Submission #1291956
Source Code Expand
//It is made by ljh2000
//有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <ctime>
#define lc root<<1
#define rc root<<1|1
using namespace std;
typedef long long LL;
const int MAXN = 200011;
int n,Q;
struct node{ LL set,add,sum; }a[MAXN*3];
inline void update(int root){ a[root].sum=a[lc].sum+a[rc].sum; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void pushdown(int root,int l,int r){
if(a[root].set==0 && a[root].add==0) return ; if(l==r) return ;
int mid=(l+r)>>1;
if(a[root].set>0) {
a[lc].set=a[rc].set=a[root].set;
a[lc].sum=1LL*a[root].set*(mid-l+1); a[rc].sum=1LL*a[root].set*(r-mid);
a[lc].add=a[rc].add=a[root].set=0;
}
if(a[root].add>0) {
a[lc].add+=a[root].add; a[rc].add+=a[root].add;
a[lc].sum+=1LL*a[root].add*(mid-l+1); a[rc].sum+=1LL*a[root].add*(r-mid);
a[root].add=0;
}
}
inline void modify(int root,int l,int r,int ql,int qr,LL val){
pushdown(root,l,r);
if(ql<=l && r<=qr) {
a[root].set=val; a[root].add=0;
a[root].sum=1LL*(r-l+1)*val;
return ;
}
int mid=(l+r)>>1;
if(ql<=mid) modify(lc,l,mid,ql,qr,val);
if(qr>mid) modify(rc,mid+1,r,ql,qr,val);
update(root);
}
inline void add(int root,int l,int r,int ql,int qr,LL val){
pushdown(root,l,r);
if(ql<=l && r<=qr) {
a[root].sum+=1LL*val*(r-l+1);
a[root].add+=val;
return ;
}
int mid=(l+r)>>1;
if(ql<=mid) add(lc,l,mid,ql,qr,val);
if(qr>mid) add(rc,mid+1,r,ql,qr,val);
update(root);
}
inline LL query(int root,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return a[root].sum;
pushdown(root,l,r); int mid=(l+r)>>1;
if(qr<=mid) return query(lc,l,mid,ql,qr);
else if(ql>mid) return query(rc,mid+1,r,ql,qr);
return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
}
inline void dfs(int root,int l,int r){
if(l==r) { printf("%lld\n",a[root].sum); return ; }
pushdown(root,l,r); int mid=(l+r)>>1;
dfs(lc,l,mid); dfs(rc,mid+1,r);
}
inline void work(){
n=getint(); Q=getint(); int x; LL y; int l,r,mid,pos;
while(Q--) {
x=getint(); scanf("%lld",&y);
if(x==1) { add(1,1,n,1,1,y); continue; }
l=1; r=x; pos=0;
while(l<=r) {
mid=(l+r)>>1;
if(1LL*query(1,1,n,mid,mid)*(x-mid+1)-query(1,1,n,mid,x) <= y) r=mid-1;
else l=mid+1,pos=mid;
}
y-=1LL*query(1,1,n,pos+1,pos+1)*(x-pos)-query(1,1,n,pos+1,x);
modify(1,1,n,pos+1,x, query(1,1,n,pos+1,pos+1) );
if(y/(x-pos)) add(1,1,n,pos+1,x,y/(x-pos));
if(y%(x-pos)) add(1,1,n,pos+1,pos+y%(x-pos),1);
}
dfs(1,1,n);
}
int main()
{
work();
return 0;
}
//有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
Submission Info
Submission Time
2017-05-17 20:13:08+0900
Task
F - Sushi
User
ljh2000
Language
C++14 (GCC 5.4.1)
Score
1200
Code Size
3074 Byte
Status
AC
Exec Time
678 ms
Memory
9728 KB
Compile Error
./Main.cpp: In function ‘void work()’:
./Main.cpp:84:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
x=getint(); scanf("%lld",&y);
^
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
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
AC
1 ms
256 KB
sub1_5.txt
AC
1 ms
256 KB
sub1_6.txt
AC
1 ms
256 KB
sub1_7.txt
AC
1 ms
256 KB
sub1_8.txt
AC
1 ms
256 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
AC
1 ms
256 KB
sub2_5.txt
AC
1 ms
256 KB
sub2_6.txt
AC
1 ms
256 KB
sub2_7.txt
AC
1 ms
256 KB
sub2_8.txt
AC
1 ms
256 KB
sub3_1.txt
AC
5 ms
640 KB
sub3_2.txt
AC
5 ms
640 KB
sub3_3.txt
AC
50 ms
1792 KB
sub3_4.txt
AC
50 ms
1792 KB
sub3_5.txt
AC
562 ms
8576 KB
sub3_6.txt
AC
597 ms
8576 KB
sub3_7.txt
AC
416 ms
8576 KB
sub3_8.txt
AC
467 ms
8576 KB
sub3_9.txt
AC
66 ms
2560 KB
sub4_1.txt
AC
677 ms
9728 KB
sub4_2.txt
AC
674 ms
9728 KB
sub4_3.txt
AC
677 ms
9728 KB
sub4_4.txt
AC
502 ms
9600 KB
sub4_5.txt
AC
678 ms
9728 KB
sub4_6.txt
AC
329 ms
9728 KB