Submission #1227883
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define NN 100400
long long oo;
struct node{
int l,r;
long long max,min;
long long sum;
int fg;
}tree[NN*4];
int n,q;
void Init(int l,int r,int idd){
tree[idd].l=l;
tree[idd].r=r;
tree[idd].max=tree[idd].min=0;
tree[idd].sum=0;
tree[idd].fg=0;
if(r-l<=1) return ;
int mid=(l+r)/2;
Init(l,mid,idd<<1);
Init(mid,r,idd<<1|1);
}
void Up(int idd){
tree[idd].sum=tree[idd<<1].sum+tree[idd<<1|1].sum;
tree[idd].max=max(tree[idd<<1].max,tree[idd<<1|1].max);
tree[idd].min=min(tree[idd<<1].min,tree[idd<<1|1].min);
}
void Down(int idd){
if(tree[idd].fg){
tree[idd<<1].fg=tree[idd<<1|1].fg=1;
tree[idd<<1].min=tree[idd<<1|1].min=tree[idd].min;
tree[idd<<1].max=tree[idd<<1|1].max=tree[idd].max;
tree[idd<<1].sum=tree[idd].min*(tree[idd<<1].r-tree[idd<<1].l);
tree[idd<<1|1].sum=tree[idd].min*(tree[idd<<1|1].r-tree[idd<<1|1].l);
tree[idd].fg=0;
}
}
long long u;
int bg;
long long ssum;
long long ftt;
void Date(int l,int r,int rr,long long num,long long pre,int idd){
long long ssum=num+tree[idd].sum+ftt;
long long avg=ssum/(rr-l);
if(ssum-avg*(rr-l)) avg++;
if(avg>pre) return ;
if(u==-1&&tree[idd].max<=avg) u=avg,bg=l;
else if(u>=avg&&tree[idd].max<=avg)u=avg,bg=l;
// printf("~%d %d %d %lld %lld %lld\n",l,r,bg,u,ssum,pre);
if(r-l<=1) return ;
Down(idd);
int mid=(l+r)/2;
if(tree[idd<<1].min*(rr-tree[idd<<1|1].l)>=tree[idd<<1|1].sum+num) Date(mid,r,rr,num,tree[idd<<1].min,idd<<1|1);
else {
ftt+=tree[idd<<1|1].sum;
Date(l,mid,rr,num,pre,idd<<1);
}
Up(idd);
}
void Update(int l,int r,int rr,long long num,long long pre,int idd){
if(tree[idd].l==l&&tree[idd].r==r){
Date(l,r,rr,num,pre,idd);
ftt+=tree[idd].sum;
return;
}
Down(idd);
int mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
Update(l,r,rr,num,pre,idd<<1);
else if(mid<=l)
Update(l,r,rr,num,tree[idd<<1].min,idd<<1|1);
else{
Update(mid,r,rr,num,tree[idd<<1].min,idd<<1|1);
Update(l,mid,rr,num,pre,idd<<1);
}
Up(idd);
}
void Query(int l,int r,int idd){
if(tree[idd].l==l&&tree[idd].r==r){
ssum+=tree[idd].sum;
return;
}
Down(idd);
int mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
Query(l,r,idd<<1);
else if(mid<=l)
Query(l,r,idd<<1|1);
else{
Query(l,mid,idd<<1);
Query(mid,r,idd<<1|1);
}
Up(idd);
}
void fugai(int l,int r,long long shu,int idd){
if(tree[idd].l==l&&tree[idd].r==r){
tree[idd].max=tree[idd].min=shu;
tree[idd].sum=(r-l)*shu;
tree[idd].fg=1;
return;
}
Down(idd);
int mid=(tree[idd].l+tree[idd].r)/2;
if(mid>=r)
fugai(l,r,shu,idd<<1);
else if(mid<=l)
fugai(l,r,shu,idd<<1|1);
else{
fugai(l,mid,shu,idd<<1);
fugai(mid,r,shu,idd<<1|1);
}
Up(idd);
}
void Print(int l,int r,int idd){
if(r-l<=1) {
printf("%lld\n",tree[idd].sum);
return;
}
Down(idd);
int mid=(r+l)/2;
Print(l,mid,idd<<1);
Print(mid,r,idd<<1|1);
Up(idd);
}
int main(){
oo=1LL*2000000*10000000+10;
scanf("%d%d",&n,&q);
Init(1,n+1,1);
for(int i=1;i<=q;i++){
int x;long long y;
scanf("%d%lld",&x,&y);
u=-1;bg=-1;
ftt=0;
Update(1,x+1,x+1,y,oo,1);
ssum=0;
Query(bg,x+1,1);
int num=(x+1)-bg;
long long sum=ssum+y;
long long avg=sum/num;
int a1=sum-avg*num;
if(a1){
fugai(bg,bg+a1,avg+1,1);
}
fugai(bg+a1,x+1,avg,1);
// Print(1,n+1,1);
}
Print(1,n+1,1);
return 0;
}
Submission Info
Submission Time
2017-04-18 12:23:31+0900
Task
F - Sushi
User
yingpingan
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
3450 Byte
Status
RE
Exec Time
297 ms
Memory
13824 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:128:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&q);
^
./Main.cpp:132:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld",&x,&y);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
Subtask3
Subtask4
Score / Max Score
0 / 0
0 / 60
0 / 400
0 / 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
1 ms
256 KB
sample_2.txt
AC
1 ms
256 KB
sample_3.txt
AC
1 ms
256 KB
sample_4.txt
AC
1 ms
256 KB
sub1_1.txt
AC
1 ms
256 KB
sub1_2.txt
AC
1 ms
256 KB
sub1_3.txt
AC
1 ms
256 KB
sub1_4.txt
RE
97 ms
6400 KB
sub1_5.txt
RE
97 ms
6400 KB
sub1_6.txt
RE
97 ms
6400 KB
sub1_7.txt
RE
96 ms
6400 KB
sub1_8.txt
RE
97 ms
6400 KB
sub1_9.txt
AC
1 ms
256 KB
sub2_1.txt
AC
1 ms
256 KB
sub2_2.txt
AC
1 ms
256 KB
sub2_3.txt
AC
1 ms
256 KB
sub2_4.txt
RE
97 ms
6400 KB
sub2_5.txt
RE
96 ms
6400 KB
sub2_6.txt
RE
96 ms
6400 KB
sub2_7.txt
AC
1 ms
256 KB
sub2_8.txt
RE
98 ms
6400 KB
sub3_1.txt
RE
98 ms
7040 KB
sub3_2.txt
RE
97 ms
7040 KB
sub3_3.txt
RE
99 ms
8448 KB
sub3_4.txt
RE
99 ms
8448 KB
sub3_5.txt
RE
108 ms
12544 KB
sub3_6.txt
RE
107 ms
12544 KB
sub3_7.txt
AC
297 ms
12672 KB
sub3_8.txt
AC
159 ms
12672 KB
sub3_9.txt
AC
86 ms
12672 KB
sub4_1.txt
RE
100 ms
12544 KB
sub4_2.txt
RE
100 ms
12544 KB
sub4_3.txt
RE
99 ms
12544 KB
sub4_4.txt
AC
164 ms
13696 KB
sub4_5.txt
RE
100 ms
12544 KB
sub4_6.txt
AC
50 ms
13824 KB