Submission #1260587


Source Code Expand

#include <stdio.h>
#include <iostream>
#include <cstring>
#define lch (x<<1)
#define rch ((x<<1)|1)
typedef long long ll;
const int N=100005;
int n,m;
ll mn[N<<2],tag[N<<2];
using namespace std;

void modify(int x,ll v){tag[x]+=v,mn[x]+=v;}
void updtag(int x){if (tag[x]) modify(lch,tag[x]),modify(rch,tag[x]),tag[x]=0;}
int find(int x,int L,int R,int l,int r,ll v)
{
	if (L<R) updtag(x);
	if (L==R) return L;
	int mid=L+R>>1;
	if (mid>=r) return find(lch,L,mid,l,r,v);
	if (mn[lch]<=v) return find(lch,L,mid,l,r,v);
	return find(rch,mid+1,R,l,r,v);
}
ll query(int x,int l,int r,int p)
{
	if (l<r) updtag(x);
	if (l==r) return mn[x];
	int mid=l+r>>1;
	if (mid>=p) return query(lch,l,mid,p);
	return query(rch,mid+1,r,p);
}
void update(int x,int L,int R,int l,int r,ll v)
{
	if (L<R) updtag(x);
	if (L>=l && R<=r){modify(x,v);return;}
	if (L>r || R<l) return;
	int mid=L+R>>1;
	update(lch,L,mid,l,r,v);
	update(rch,mid+1,R,l,r,v);
	mn[x]=mn[rch];
}
void calc(int x,int l,int r)
{
	if (l<r) updtag(x);
	if (l==r){printf ("%lld\n",mn[x]);return;}
	int mid=l+r>>1;
	calc(lch,l,mid),calc(rch,mid+1,r);
}
int main()
{
	#ifdef Kay
		freopen ("s8pc_3_f.in","r",stdin);
		freopen ("s8pc_3_f.out","w",stdout);
	#endif
	scanf ("%d %d",&n,&m);
	int pos;ll tot;
	while (m--)
	{
		scanf ("%d %lld",&pos,&tot);
		while (tot)
		{
			ll val=query(1,1,n,pos);
			int las=find(1,1,n,1,pos,val);
			if (las==1)
			{
				update(1,1,n,1,pos,tot/pos),tot%=pos;
				if (tot) update(1,1,n,1,tot,1);
				break;
			}
			ll lv=query(1,1,n,las-1);
			ll add=min(lv-val,tot/(pos-las+1));
			update(1,1,n,las,pos,add),tot-=add*(pos-las+1);
			val+=add;
			if (val<lv && tot){update(1,1,n,las,las+tot-1,1);break;}
		}
	}
	calc(1,1,n);
	return 0;
}

Submission Info

Submission Time
Task F - Sushi
User AHWHRKY
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 1794 Byte
Status AC
Exec Time 336 ms
Memory 7808 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&m);
                       ^
./Main.cpp:58:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %lld",&pos,&tot);
                              ^

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 60 / 60 400 / 400 240 / 240 500 / 500
Status
AC × 4
AC × 9
AC × 21
AC × 18
AC × 36
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
Subtask1 sample_3, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt
Subtask3 sample_3, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub3_7.txt, sub3_8.txt, sub3_9.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub2_7.txt, sub2_8.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub3_7.txt, sub3_8.txt, sub3_9.txt, sub4_1.txt, sub4_2.txt, sub4_3.txt, sub4_4.txt, sub4_5.txt, sub4_6.txt
Case Name Status Exec Time Memory
sample_1.txt AC 2 ms 2304 KB
sample_2.txt AC 2 ms 2304 KB
sample_3.txt AC 2 ms 2304 KB
sample_4.txt AC 2 ms 2304 KB
sub1_1.txt AC 2 ms 2304 KB
sub1_2.txt AC 2 ms 2304 KB
sub1_3.txt AC 2 ms 2304 KB
sub1_4.txt AC 2 ms 2304 KB
sub1_5.txt AC 2 ms 2304 KB
sub1_6.txt AC 2 ms 2304 KB
sub1_7.txt AC 2 ms 2304 KB
sub1_8.txt AC 2 ms 2304 KB
sub1_9.txt AC 2 ms 2304 KB
sub2_1.txt AC 2 ms 2304 KB
sub2_2.txt AC 2 ms 2304 KB
sub2_3.txt AC 2 ms 2304 KB
sub2_4.txt AC 2 ms 2304 KB
sub2_5.txt AC 2 ms 2304 KB
sub2_6.txt AC 2 ms 2304 KB
sub2_7.txt AC 2 ms 2304 KB
sub2_8.txt AC 2 ms 2304 KB
sub3_1.txt AC 3 ms 2432 KB
sub3_2.txt AC 3 ms 2432 KB
sub3_3.txt AC 16 ms 2816 KB
sub3_4.txt AC 16 ms 2816 KB
sub3_5.txt AC 138 ms 6528 KB
sub3_6.txt AC 138 ms 6528 KB
sub3_7.txt AC 81 ms 6016 KB
sub3_8.txt AC 127 ms 6528 KB
sub3_9.txt AC 82 ms 4608 KB
sub4_1.txt AC 334 ms 7680 KB
sub4_2.txt AC 334 ms 7808 KB
sub4_3.txt AC 335 ms 7680 KB
sub4_4.txt AC 196 ms 7552 KB
sub4_5.txt AC 336 ms 7680 KB
sub4_6.txt AC 58 ms 7680 KB