oj.uz

Submission #84634

# Submission time Handle Problem Language Result Execution time Memory
84634 2018-11-16T08:19:23 Z farukkastamonuda Trading (IZhO13_trading) C++14
100 / 100
 477 ms 45684 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 300005
#define ii pair<int,int>
#define mid (start+end)/2
using namespace std;
int n,m,l,r,x,tree[li*4],lazy[li*4];
void push(int node,int start,int end){
	if(lazy[node]==0) return ;
	tree[node]=max(tree[node],lazy[node]);
	if(start!=end){
		lazy[node*2]=max(lazy[node*2],lazy[node]-(end-mid));
		lazy[node*2+1]=max(lazy[node*2+1],lazy[node]);
	}
	lazy[node]=0;
}
void update(int node,int start,int end,int l,int r,int val){
	push(node,start,end);
	if(start>end || start>r || end<l) return ;
	if(start>=l && end<=r){
		lazy[node]=max(lazy[node],val-(r-end));
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l) return -inf;
	push(node,start,end);
	if(start>=l && end<=r) return tree[node];
	return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&l,&r,&x);
		update(1,1,n,l,r,x+r-l);
	}
	for(int i=1;i<=n;i++){
		printf("%d ",query(1,1,n,i,i));
	}
	return 0;
}

Compilation message

trading.cpp: In function 'int main()':
trading.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
trading.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&l,&r,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 5 ms 648 KB Output is correct
7 Correct 243 ms 7112 KB Output is correct
8 Correct 261 ms 11352 KB Output is correct
9 Correct 269 ms 14152 KB Output is correct
10 Correct 304 ms 16020 KB Output is correct
11 Correct 304 ms 22520 KB Output is correct
12 Correct 344 ms 24900 KB Output is correct
13 Correct 351 ms 30132 KB Output is correct
14 Correct 373 ms 33212 KB Output is correct
15 Correct 384 ms 38692 KB Output is correct
16 Correct 411 ms 42316 KB Output is correct
17 Correct 401 ms 44644 KB Output is correct
18 Correct 404 ms 45684 KB Output is correct
19 Correct 426 ms 45684 KB Output is correct
20 Correct 477 ms 45684 KB Output is correct