Submission #554194

#	Time	Username	Problem	Language	Result	Execution time	Memory
554194		MilosMilutinovic	Trading (IZhO13_trading)	C++14	100 / 100	234 ms	17288 KiB

trading

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair

const int N=300050;
const int M=2*N;

int n,m,root,ls[M],rs[M],tsz;
pii st[M];

void Build(int&c,int ss,int se){
	c=++tsz;
	st[c]=(ss==se?mp(ss,0):mp(n+1,0));
	if(ss==se)return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void Set(int c,int ss,int se,int qs,int qe,pii x){
	if(ss>se||ss>qe||se<qs)return;
	if(qs<=ss&&se<=qe){
		if(ss-st[c].first+st[c].second<ss-x.first+x.second)st[c]=x;
		return;
	}
	int mid=ss+se>>1;
	Set(ls[c],ss,mid,qs,qe,x);
	Set(rs[c],mid+1,se,qs,qe,x);
}
void Solve(int c,int ss,int se,pii mx){
	if(ss-mx.first+mx.second<ss-st[c].first+st[c].second)mx=st[c];
	if(ss==se){
		printf("%i ",ss-mx.first+mx.second);
		return;
	}
	int mid=ss+se>>1;
	Solve(ls[c],ss,mid,mx);
	Solve(rs[c],mid+1,se,mx);
}

int main(){
	scanf("%i%i",&n,&m);
	Build(root,1,n);
	while(m--){
		int l,r,x;scanf("%i%i%i",&l,&r,&x);
		Set(root,1,n,l,r,{l,x});
	}
	Solve(root,1,n,{n+1,0});
	return 0;
}

Compilation message (stderr)

trading.cpp: In function 'void Build(int&, int, int)':
trading.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |  int mid=ss+se>>1;
      |          ~~^~~
trading.cpp: In function 'void Set(int, int, int, int, int, std::pair<int, int>)':
trading.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |  int mid=ss+se>>1;
      |          ~~^~~
trading.cpp: In function 'void Solve(int, int, int, std::pair<int, int>)':
trading.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int mid=ss+se>>1;
      |          ~~^~~
trading.cpp: In function 'int main()':
trading.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%i%i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
trading.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   int l,r,x;scanf("%i%i%i",&l,&r,&x);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100