oj.uz

Submission #336538

# Submission time Handle Problem Language Result Execution time Memory
336538 2020-12-15T15:01:15 Z katearima Trading (IZhO13_trading) C++14
0 / 100
 406 ms 5228 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[2*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;
	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;
	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:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      |      ^

Subtask #1
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 384 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 235 ms 3948 KB Output is correct
8 Correct 263 ms 5100 KB Output is correct
9 Correct 271 ms 4332 KB Output is correct
10 Correct 290 ms 2540 KB Output is correct
11 Correct 300 ms 5228 KB Output is correct
12 Correct 332 ms 3692 KB Output is correct
13 Correct 348 ms 4716 KB Output is correct
14 Correct 348 ms 3692 KB Output is correct
15 Correct 395 ms 4432 KB Output is correct
16 Correct 406 ms 4204 KB Output is correct
17 Runtime error 3 ms 1516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -