# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
27245 |
2017-07-11T13:08:58 Z |
TAMREF |
Trading (IZhO13_trading) |
C++11 |
|
519 ms |
11400 KB |
#include <bits/stdc++.h>
using namespace std;
const int mx=300005, ms=1048577;
struct Segtree{
int a[mx],seg[ms],lz[ms];
int i,v,l,r;
Segtree(){
memset(a,0,sizeof(a));
fill(seg,seg+ms,INT_MIN);
fill(lz,lz+ms,INT_MIN);
}
int rmq(int n, int s, int e){
if(lz[n]!=INT_MIN){
seg[n]=max(seg[n],lz[n]);
if(s!=e){
lz[n<<1]=max(lz[n<<1],lz[n]);
lz[n<<1|1]=max(lz[n<<1|1],lz[n]);
} lz[n]=INT_MIN;
}
if(i<s||i>e) return INT_MIN;
if(s==i&&i==e) return seg[n];
int m=(s+e)>>1;
return seg[n]=max(rmq(n<<1,s,m),rmq(n<<1|1,m+1,e));
}
void update(int n, int s, int e){
if(lz[n]!=INT_MIN){
seg[n]=max(seg[n],lz[n]);
if(s!=e){
lz[n<<1]=max(lz[n<<1],lz[n]);
lz[n<<1|1]=max(lz[n<<1|1],lz[n]);
} lz[n]=INT_MIN;
}
if(s>r||e<l) return;
if(l<=s&&e<=r){
seg[n]=max(seg[n],v);
if(s!=e){
lz[n<<1]=max(lz[n<<1],v);
lz[n<<1|1]=max(lz[n<<1|1],v);
}
return;
}
int y=(s+e)>>1;
update(n<<1,s,y);
update(n<<1|1,y+1,e);
seg[n]=max(seg[n<<1],seg[n<<1|1]);
}
} S;
int main(){
int N,M;
for(scanf("%d%d",&N,&M);M--;){
scanf("%d%d%d",&S.l,&S.r,&S.v);
S.v-=S.l;
S.update(1,1,N);
}
for(S.i=1;S.i<=N;S.i++){
int t=S.rmq(1,1,N);
printf("%d ",(t==INT_MIN)?0:t+S.i);
}
}
Compilation message
trading.cpp: In function 'int main()':
trading.cpp:50:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d%d",&N,&M);M--;){
^
trading.cpp:51:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&S.l,&S.r,&S.v);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
11400 KB |
Output is correct |
2 |
Correct |
3 ms |
11400 KB |
Output is correct |
3 |
Correct |
0 ms |
11400 KB |
Output is correct |
4 |
Correct |
0 ms |
11400 KB |
Output is correct |
5 |
Correct |
0 ms |
11400 KB |
Output is correct |
6 |
Correct |
6 ms |
11400 KB |
Output is correct |
7 |
Correct |
246 ms |
11400 KB |
Output is correct |
8 |
Correct |
299 ms |
11400 KB |
Output is correct |
9 |
Correct |
306 ms |
11400 KB |
Output is correct |
10 |
Correct |
303 ms |
11400 KB |
Output is correct |
11 |
Correct |
299 ms |
11400 KB |
Output is correct |
12 |
Correct |
319 ms |
11400 KB |
Output is correct |
13 |
Correct |
329 ms |
11400 KB |
Output is correct |
14 |
Correct |
316 ms |
11400 KB |
Output is correct |
15 |
Correct |
463 ms |
11400 KB |
Output is correct |
16 |
Correct |
419 ms |
11400 KB |
Output is correct |
17 |
Correct |
333 ms |
11400 KB |
Output is correct |
18 |
Correct |
389 ms |
11400 KB |
Output is correct |
19 |
Correct |
493 ms |
11400 KB |
Output is correct |
20 |
Correct |
519 ms |
11400 KB |
Output is correct |