Submission #4811

#	Time	Username	Problem	Language	Result	Execution time	Memory
4811		cki86201	Trading (IZhO13_trading)	C++98	100 / 100	196 ms	5184 KiB

trading

#include<stdio.h>
#include<algorithm>
using namespace std;

const int N_ = 1<<19;

int T[1<<20];

void update(int a,int b,int w)
{
	a+=N_, b+=N_;
	while(a<=b){
		if(a&1)T[a] = max(T[a],w);
		if((b&1)==0)T[b] = max(T[b],w);
		a = (a+1)>>1;
		b = (b-1)>>1;
	}
}

int read(int x)
{
	int ret = -1e7;
	x+=N_;
	while(x){
		ret = max(ret,T[x]);
		x>>=1;
	}
	return ret;
}

int main(){
	int n,m,i;
	scanf("%d%d",&n,&m);
	for(i=0;i<1<<20;i++)T[i]=-1e7;
	for(i=1;i<=n;i++)update(i,i,-i);
	for(i=0;i<m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		update(x,y,z-x);
	}
	for(i=1;i<=n;i++){
		printf("%d ",read(i)+i);
	}
	return 0;
}

• Subtask 1: 100 / 100