Submission #1271361
Source Code Expand
#include <bits/stdc++.h>
#define sum(x,y) que(1,1,n,x,y)
#define change(x,y,z) chan(1,1,n,x,y,z)
#define add(x,y,z) Plus(1,1,n,x,y,z)
#define mid (l+r>>1)
using namespace std;
int sum[400000],fg[400000],ad[400000];
int n,m,a,b;
void down(int now,int l,int r)
{
if(fg[now])
{
fg[now]+=ad[now];
fg[now<<1]=fg[now];
fg[now<<1|1]=fg[now];
ad[now]=ad[now<<1]=ad[now<<1|1]=fg[now]=0;
sum[now<<1]=fg[now<<1]*(mid-l+1);
sum[now<<1|1]=fg[now<<1|1]*(r-mid);
}
if(ad[now])
{
ad[now<<1]+=ad[now];
ad[now<<1|1]+=ad[now];
sum[now<<1]+=ad[now]*(mid-l+1);
sum[now<<1|1]+=ad[now]*(r-mid);
ad[now]=0;
}
}
void updata(int now)
{
sum[now]=sum[now<<1]+sum[now<<1|1];
}
void chan(int now,int l,int r,int x,int y,int z)
{
if(l==x && r==y)
{
fg[now]=z;
ad[now]=0;
sum[now]=z*(r-l+1);
return;
}
down(now,l,r);
if(x<=mid)
chan(now<<1,l,mid,x,min(mid,y),z);
if(y>mid)
chan(now<<1|1,mid+1,r,max(mid+1,x),y,z);
updata(now);
}
void Plus(int now,int l,int r,int x,int y,int z)
{
if(l==x && r==y)
{
ad[now]+=z;
sum[now]+=z*(r-l+1);
return;
}
down(now,l,r);
if(x<=mid)
Plus(now<<1,l,mid,x,min(mid,y),z);
if(y>mid)
Plus(now<<1|1,mid+1,r,max(mid+1,x),y,z);
updata(now);
}
int que(int now,int l,int r,int x,int y)
{
if(l==x && r==y)
return sum[now];
down(now,l,r);
int ret=0;
if(x<=mid)
ret+=que(now<<1,l,mid,x,min(y,mid));
if(y>mid)
ret+=que(now<<1|1,mid+1,r,max(x,mid+1),y);
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
int l=1,r=a;
for(;l<r;)
if(sum(mid,mid)*(a-mid+1)-sum(mid,a)<=b)
r=mid;
else
l=mid+1;
b-=sum(l,l)*(a-l+1)-sum(l,a);
change(l,a,sum(l,l));
add(l,a,b/(a-l+1));
if(b%(a-l+1))
add(l,l+b%(a-l+1)-1,1);
}
for(int i=1;i<=n;i++)
printf("%d\n",sum(i,i));
return 0;
}
Submission Info
Submission Time
2017-05-09 16:35:38+0900
Task
F - Sushi
User
wanglichao1121
Language
C++14 (GCC 5.4.1)
Score
300
Code Size
1903 Byte
Status
RE
Exec Time
839 ms
Memory
4992 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:78:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:81:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Subtask3
Subtask4
Score / Max Score
0 / 0
60 / 60
0 / 400
240 / 240
0 / 500
Status
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
1 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
1 ms
2304 KB
sub2_2.txt
AC
2 ms
2304 KB
sub2_3.txt
AC
2 ms
2304 KB
sub2_4.txt
RE
98 ms
2304 KB
sub2_5.txt
RE
96 ms
2304 KB
sub2_6.txt
RE
97 ms
2304 KB
sub2_7.txt
WA
2 ms
2304 KB
sub2_8.txt
WA
2 ms
2304 KB
sub3_1.txt
AC
7 ms
2432 KB
sub3_2.txt
AC
7 ms
2432 KB
sub3_3.txt
AC
75 ms
2816 KB
sub3_4.txt
AC
75 ms
2816 KB
sub3_5.txt
AC
839 ms
4096 KB
sub3_6.txt
AC
838 ms
4096 KB
sub3_7.txt
AC
702 ms
4096 KB
sub3_8.txt
AC
751 ms
4096 KB
sub3_9.txt
AC
135 ms
2432 KB
sub4_1.txt
RE
97 ms
2816 KB
sub4_2.txt
RE
100 ms
3328 KB
sub4_3.txt
RE
97 ms
3072 KB
sub4_4.txt
WA
695 ms
4864 KB
sub4_5.txt
WA
790 ms
4992 KB
sub4_6.txt
WA
478 ms
4864 KB