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
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
AC × 2
AC × 7
AC × 14
AC × 33
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