Submission #338468
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#define SIZE 200005
#define BT 256*1024*2
#define INF 100000000000000000LL
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
typedef pair <P,int> PP;
int val[SIZE];
int get(P p,int v)
{
if(p.first%2==p.second%2)
{
if(p.first%2==1) return v;
return -v;
}
return 0;
}
int main()
{
int n;
scanf("%d",&n);
ll all=0;
for(int i=0;i<n;i++)
{
scanf("%d",&val[i]);
if(i!=n-1)
{
if(i%2==0)
{
all+=val[i];
}
}
else
{
if(n%2==0) all+=val[i];
}
}
set <PP> st;
set <PP>::iterator it,its;
ll sum=0;
for(int i=n-2;i>0;)
{
int v;
if(i==n-2) v=min(val[n-2],val[n-1]);
else v=val[i];
int s=i;
for(;i>0&&val[i]>=v;i--);
st.insert(PP(P(i+1,s),v));
sum+=get(P(i+1,s),v);
}
printf("%lld\n",all+sum);
int q;
scanf("%d",&q);
for(int i=0;i<q;i++)
{
int p,g;
scanf("%d %d",&p,&g);p--;
val[p]-=g;
if(p%2==0||(n%2==0&&p==n-1)) sum-=g;
if(p>0)
{
if(p==n-1) p=n-2;
int v;
if(p>=n-2) v=min(val[n-2],val[n-1]);
else v=val[p];
it=st.upper_bound(PP(P(p+1,-1),-1));it--;
if(it->second>v)
{
P q=it->first;
if(q.second>p)
{
st.insert(PP(P(p+1,q.second),it->second));
}
int end=q.first;
sum-=get(P(q.first,p),it->second);
sum+=get(P(q.first,p),v);
if(it==st.begin()) st.erase(it);
else
{
while(1)
{
its=it;its--;
st.erase(it);
it=its;
if(it->second<=v) break;
sum-=get(it->first,it->second);
sum+=get(it->first,v);
end=it->first.first;
if(it==st.begin())
{
st.erase(it);
break;
}
}
}
st.insert(PP(P(end,p),v));
}
}
printf("%lld\n",sum+all);
}
return 0;
}
Submission Info
Submission Time
2015-02-15 12:51:28+0900
Task
D - コインの取り合い
User
yutaka1999
Language
C++ (G++ 4.6.4)
Score
180
Code Size
1957 Byte
Status
AC
Exec Time
592 ms
Memory
15312 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:36:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:64:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:68:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
Sample
Subtask1
Subtask2
Subtask3
Score / Max Score
0 / 0
10 / 10
80 / 80
90 / 90
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt
Subtask1
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
Subtask2
sample_01.txt, sample_02.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
502 ms
1868 KB
sample_02.txt
AC
36 ms
1868 KB
subtask1_01.txt
AC
39 ms
1868 KB
subtask1_02.txt
AC
83 ms
2632 KB
subtask1_03.txt
AC
101 ms
6388 KB
subtask1_04.txt
AC
127 ms
7884 KB
subtask1_05.txt
AC
83 ms
2760 KB
subtask1_06.txt
AC
65 ms
2628 KB
subtask1_07.txt
AC
213 ms
15172 KB
subtask2_01.txt
AC
36 ms
1912 KB
subtask2_02.txt
AC
174 ms
2244 KB
subtask2_03.txt
AC
68 ms
2632 KB
subtask2_04.txt
AC
189 ms
2636 KB
subtask2_05.txt
AC
189 ms
2772 KB
subtask2_06.txt
AC
128 ms
2700 KB
subtask2_07.txt
AC
207 ms
2632 KB
subtask2_08.txt
AC
65 ms
2680 KB
subtask2_09.txt
AC
172 ms
2168 KB
subtask2_10.txt
AC
190 ms
2632 KB
subtask2_11.txt
AC
192 ms
2764 KB
subtask2_12.txt
AC
214 ms
2760 KB
subtask3_01.txt
AC
387 ms
2128 KB
subtask3_02.txt
AC
244 ms
2640 KB
subtask3_03.txt
AC
242 ms
2636 KB
subtask3_04.txt
AC
298 ms
2632 KB
subtask3_05.txt
AC
66 ms
2628 KB
subtask3_06.txt
AC
592 ms
15172 KB
subtask3_07.txt
AC
400 ms
15192 KB
subtask3_08.txt
AC
534 ms
15312 KB
subtask3_09.txt
AC
535 ms
15228 KB
subtask3_10.txt
AC
454 ms
15172 KB
subtask3_11.txt
AC
320 ms
5196 KB
subtask3_12.txt
AC
398 ms
7884 KB
subtask3_13.txt
AC
395 ms
7880 KB
subtask3_14.txt
AC
246 ms
2632 KB