oj.uz

Submission #336544

# Submission time Handle Problem Language Result Execution time Memory
336544 2020-12-15T15:17:05 Z katearima Trading (IZhO13_trading) C++14
100 / 100
 480 ms 7532 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],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) return;
	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(a!=b){
		findmx(2*i+1, a, mid, x);
		findmx(2*i+2, mid+1, b, x);		
	}

}

main(){


	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 0 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 4 ms 364 KB Output is correct
7 Correct 224 ms 3820 KB Output is correct
8 Correct 253 ms 4972 KB Output is correct
9 Correct 258 ms 4204 KB Output is correct
10 Correct 276 ms 2540 KB Output is correct
11 Correct 298 ms 5356 KB Output is correct
12 Correct 316 ms 3692 KB Output is correct
13 Correct 335 ms 4732 KB Output is correct
14 Correct 330 ms 3564 KB Output is correct
15 Correct 378 ms 4332 KB Output is correct
16 Correct 392 ms 4076 KB Output is correct
17 Correct 379 ms 6380 KB Output is correct
18 Correct 409 ms 7532 KB Output is correct
19 Correct 409 ms 5996 KB Output is correct
20 Correct 480 ms 7276 KB Output is correct