oj.uz

Submission #554194

# Submission time Handle Problem Language Result Execution time Memory
554194 2022-04-27T22:24:50 Z MilosMilutinovic Trading (IZhO13_trading) C++14
100 / 100
 234 ms 17288 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 444 KB Output is correct
7 Correct 111 ms 8704 KB Output is correct
8 Correct 138 ms 9760 KB Output is correct
9 Correct 132 ms 10056 KB Output is correct
10 Correct 140 ms 10572 KB Output is correct
11 Correct 157 ms 12012 KB Output is correct
12 Correct 157 ms 12108 KB Output is correct
13 Correct 185 ms 12936 KB Output is correct
14 Correct 162 ms 13052 KB Output is correct
15 Correct 187 ms 14232 KB Output is correct
16 Correct 234 ms 14588 KB Output is correct
17 Correct 177 ms 14796 KB Output is correct
18 Correct 206 ms 15544 KB Output is correct
19 Correct 204 ms 15596 KB Output is correct
20 Correct 232 ms 17288 KB Output is correct