oj.uz

Submission #336542

# Submission time Handle Problem Language Result Execution time Memory
336542 2020-12-15T15:14:06 Z nickmet2004 Trading (IZhO13_trading) C++11
100 / 100
 297 ms 13292 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N=300005;
const int M=300005;
int m,n,l,r;
ll tree[4*N+2],x,ans;
void update(int i, int a, int b, int l, int r, int x){
	if(r<a || l>b) return;
	if( a>=l && b<=r) {
		int k=a-l+x;
		if(tree[i]>k) return;
		tree[i]=k;
		return;
	}
	int mid=(a+b)/2;
	if(a!=b){
		update(2*i+1,  a,  mid, l, r, x);
		update(2*i+2, mid+1,b, l , r, x);
	}


}
void findmx(int i, int a, int b, int x){

	if(x==a && x==b) {
		ans=tree[i];
		return;
	}
	int mid=(a+b)/2;
	if(tree[i]!=0 && a!=b){
		ll k=tree[i];
		tree[2*i+1]=max(tree[2*i+1], k);
		tree[2*i+2]=max(tree[2*i+2], k+(mid+1-a));
		tree[i]=0;
	}
	if(x<a || x>b) return;
	if(a!=b){
		findmx(2*i+1, a, mid, x);
		findmx(2*i+2, mid+1, b, x);
	}

}

main(){

    ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=0; i<m; i++){
		cin>>l>>r>>x;
		l--; r--;
		update(0, 0, n-1, l, r, x);
	}
	for(int i=0; i<n; i++){
		ans=0;
		findmx(0,0,n-1,i);
		cout<<ans<<" ";
	}


}

Compilation message

trading.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main(){
      |      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 137 ms 3820 KB Output is correct
8 Correct 151 ms 5100 KB Output is correct
9 Correct 156 ms 4224 KB Output is correct
10 Correct 167 ms 2540 KB Output is correct
11 Correct 178 ms 5228 KB Output is correct
12 Correct 194 ms 3820 KB Output is correct
13 Correct 203 ms 4716 KB Output is correct
14 Correct 206 ms 3436 KB Output is correct
15 Correct 231 ms 4332 KB Output is correct
16 Correct 237 ms 4076 KB Output is correct
17 Correct 238 ms 11244 KB Output is correct
18 Correct 260 ms 12652 KB Output is correct
19 Correct 256 ms 10988 KB Output is correct
20 Correct 297 ms 13292 KB Output is correct