# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
380251 |
2021-03-20T17:21:22 Z |
cpp219 |
Trading (IZhO13_trading) |
C++14 |
|
550 ms |
45956 KB |
#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 3e5 + 9;
const ll inf = 1e16 + 7;
vector<LL> g[N];
ll n,st[4*N],lazy[4*N],L,R,val,m;
void Pass(ll id){
ll t = lazy[id]; lazy[id] = 0;
st[id*2] += t; lazy[id*2] += t;
st[id*2 + 1] += t; lazy[id*2 + 1] += t;
}
void upd(ll id,ll l,ll r,ll u,ll v,ll val){
if (v < l||r < u) return;
if (u <= l&&r <= v){
if (u == v) st[id] = val,lazy[id] = val;
else st[id] += val,lazy[id] += val;
return;
}
ll mid = (l + r)/2; Pass(id);
upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
st[id] = max(st[id*2],st[id*2 + 1]);
}
ll Get(ll id,ll l,ll r,ll u){
if (u < l||r < u) return -inf;
if (l == r) return st[id];
ll mid = (l + r)/2; Pass(id);
return max(Get(id*2,l,mid,u),Get(id*2 + 1,mid + 1,r,u));
}
void out_seg(){
for (ll i = 1;i <= m;i++) cout<<Get(1,1,m,i)<<" ";
cout<<"\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
cin>>n>>m;
for (ll i = 1;i <= m;i++){
cin>>L>>R>>val;
g[L].push_back({i,val}); g[R + 1].push_back({i,-inf});
}
for (ll i = 1;i < 4*N;i++) st[i] = -inf;
for (ll i = 1;i <= n;i++){
for (auto j : g[i]){
ll pos = j.fs,val = j.sc;
upd(1,1,m,pos,pos,val);
}
cout<<max(0ll,st[1])<<" "; upd(1,1,m,1,m,1);
}
}
Compilation message
trading.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
1 | #pragma GCC optimization "Ofast"
|
trading.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
trading.cpp: In function 'int main()':
trading.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
52 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
16748 KB |
Output is correct |
2 |
Correct |
11 ms |
16748 KB |
Output is correct |
3 |
Correct |
12 ms |
16748 KB |
Output is correct |
4 |
Correct |
12 ms |
16876 KB |
Output is correct |
5 |
Correct |
12 ms |
16876 KB |
Output is correct |
6 |
Correct |
14 ms |
17004 KB |
Output is correct |
7 |
Correct |
259 ms |
31444 KB |
Output is correct |
8 |
Correct |
287 ms |
32716 KB |
Output is correct |
9 |
Correct |
293 ms |
33228 KB |
Output is correct |
10 |
Correct |
314 ms |
33864 KB |
Output is correct |
11 |
Correct |
340 ms |
34884 KB |
Output is correct |
12 |
Correct |
356 ms |
35656 KB |
Output is correct |
13 |
Correct |
395 ms |
35904 KB |
Output is correct |
14 |
Correct |
380 ms |
36032 KB |
Output is correct |
15 |
Correct |
463 ms |
38744 KB |
Output is correct |
16 |
Correct |
490 ms |
39380 KB |
Output is correct |
17 |
Correct |
456 ms |
38400 KB |
Output is correct |
18 |
Correct |
463 ms |
42696 KB |
Output is correct |
19 |
Correct |
465 ms |
38728 KB |
Output is correct |
20 |
Correct |
550 ms |
45956 KB |
Output is correct |