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 |
|
|
|
|
|
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 |