oj.uz

Submission #689672

# Submission time Handle Problem Language Result Execution time Memory
689672 2023-01-29T05:23:46 Z sudheerays123 Trading (IZhO13_trading) C++17
100 / 100
 441 ms 36164 KB 
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 3e5+5 , INF = 1e18 , MOD = 1e9+7;

vector<ll> seg(4*N);
vector<pair<ll,ll>> lazy(4*N);

void build(ll node , ll left ,  ll right){

	if(left == right){
		seg[node] = 0;
		lazy[node].first = 0;
		lazy[node].second = 0;
		return;
	}

	ll mid = (left+right)/2;

	build(2*node,left,mid);
	build(2*node+1,mid+1,right);

	seg[node] = max(seg[2*node],seg[2*node+1]);
}


bool shouldIUpdate(ll beforeval , ll beforepos , ll newval , ll newpos , ll pos){
	if(beforepos == 0) return true;
	if(pos-beforepos+beforeval > pos-newpos+newval) return false;
	return true;
}

void update(ll node , ll left , ll right , ll ql , ll qr , ll val){

	if(lazy[node].first){
		seg[node] = max(seg[node],right-lazy[node].second+lazy[node].first);
		if(left != right){

			ll mid = (left+right)/2;

			if(shouldIUpdate(lazy[2*node].first,lazy[2*node].second,lazy[node].first,lazy[node].second,mid)){
				lazy[2*node] = lazy[node];
			}
			if(shouldIUpdate(lazy[2*node+1].first,lazy[2*node+1].second,lazy[node].first,lazy[node].second,right)){
				lazy[2*node+1] = lazy[node];
			}
		}
		lazy[node].first = 0;
		lazy[node].second = 0;
	}

	if(left >= ql && right <= qr){

		seg[node] = max(seg[node],right-ql+val);

		if(left != right){

			ll mid = (left+right)/2;

			if(shouldIUpdate(lazy[2*node].first,lazy[2*node].second,val,ql,mid)){
				lazy[2*node] = make_pair(val,ql);
			}
			if(shouldIUpdate(lazy[2*node+1].first,lazy[2*node+1].second,val,ql,right)){
				lazy[2*node+1] = make_pair(val,ql);
			}
		}
		
		return;
	}

	if(left > qr || right < ql) return;

	ll mid = (left+right)/2;

	update(2*node,left,mid,ql,qr,val);
	update(2*node+1,mid+1,right,ql,qr,val);

	seg[node] = max(seg[2*node],seg[2*node+1]);
}

ll query(ll node , ll left , ll right , ll ql , ll qr){

	if(lazy[node].first){
		seg[node] = max(seg[node],right-lazy[node].second+lazy[node].first);
		if(left != right){

			ll mid = (left+right)/2;

			if(shouldIUpdate(lazy[2*node].first,lazy[2*node].second,lazy[node].first,lazy[node].second,mid)){
				lazy[2*node] = lazy[node];
			}
			if(shouldIUpdate(lazy[2*node+1].first,lazy[2*node+1].second,lazy[node].first,lazy[node].second,right)){
				lazy[2*node+1] = lazy[node];
			}
		}
		lazy[node].first = 0;
		lazy[node].second = 0;
	}

	if(left >= ql && right <= qr) return seg[node];
	if(left > qr || right < ql) return 0;

	ll mid = (left+right)/2;

	ll l = query(2*node,left,mid,ql,qr);
	ll r = query(2*node+1,mid+1,right,ql,qr);

	return max(l,r);
}

void solve(){

	ll n,m;
	cin >> n >> m;

	build(1,1,n);

	while(m--){
		ll l,r,x;
		cin >> l >> r >> x;

		update(1,1,n,l,r,x);
	}

	for(ll i = 1; i <= n; i++) cout << query(1,1,n,i,i) << " ";
}

int main(){

	fast;

	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();

	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 16 ms 28452 KB Output is correct
3 Correct 14 ms 28580 KB Output is correct
4 Correct 13 ms 28500 KB Output is correct
5 Correct 13 ms 28520 KB Output is correct
6 Correct 14 ms 28500 KB Output is correct
7 Correct 233 ms 32176 KB Output is correct
8 Correct 254 ms 32716 KB Output is correct
9 Correct 234 ms 32716 KB Output is correct
10 Correct 263 ms 32764 KB Output is correct
11 Correct 257 ms 33596 KB Output is correct
12 Correct 328 ms 33612 KB Output is correct
13 Correct 298 ms 34000 KB Output is correct
14 Correct 356 ms 33860 KB Output is correct
15 Correct 354 ms 34624 KB Output is correct
16 Correct 391 ms 34724 KB Output is correct
17 Correct 384 ms 34748 KB Output is correct
18 Correct 387 ms 35300 KB Output is correct
19 Correct 384 ms 34888 KB Output is correct
20 Correct 441 ms 36164 KB Output is correct