oj.uz

Submission #339721

# Submission time Handle Problem Language Result Execution time Memory
339721 2020-12-26T04:54:38 Z tengiz05 Trading (IZhO13_trading) C++17
100 / 100
 425 ms 5740 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 3e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k, sz=1;
struct node{
	int prl, prr;
};
node t[N*4];
void prop(int x, int len){
	if(t[x].prl == 0)return;
	if(len == 1){
		assert(t[x].prl == t[x].prr);
		chmax(a[x-sz],t[x].prl);
	}else {
		int mid = (t[x].prr+t[x].prl)>>1;
		assert(mid >= t[x].prl && mid <= t[x].prr);
		chmax(t[x<<1].prl,t[x].prl);
		chmax(t[x<<1].prr,mid);
		chmax(t[x<<1|1].prl,mid+1);
		chmax(t[x<<1|1].prr,t[x].prr);
	}t[x].prl = 0;
	t[x].prr = 0;
}
int toup;
void update(int l, int r, int L, int R, int x){
	prop(x, R-L);
	if(L >= r || R <= l)return;
	if(L >= l && R <= r){
		t[x].prl = toup;
		toup += R-L;
		t[x].prr = toup-1;
		prop(x, R-L);
		return;
	}int mid = (L+R)/2;
	update(l, r, L, mid, x<<1);
	update(l, r, mid, R, x<<1|1);
}

void solve(int test_case){
	int i, j;
	cin >> n >> m;
	while(sz < n)sz<<=1;
	while(m --){
		int l, r, x;
		cin >> l >> r >> x;
		toup = x;
		l--;
		update(l, r, 0, sz, 1);
	}
	int S = sz;
	int cnt = 2;
	for(i=1;i<sz*2;i++){
		assert(S);
		prop(i, S);
		if(__builtin_popcount(cnt) == 1)S>>=1;
		cnt++;
	}
	for(i=0;i<n;i++)cout << a[i] << ' ' ;
	cout << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

trading.cpp: In function 'void solve(int)':
trading.cpp:52:9: warning: unused variable 'j' [-Wunused-variable]
   52 |  int i, j;
      |         ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 396 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 189 ms 3180 KB Output is correct
8 Correct 220 ms 4460 KB Output is correct
9 Correct 222 ms 3692 KB Output is correct
10 Correct 240 ms 2540 KB Output is correct
11 Correct 259 ms 5224 KB Output is correct
12 Correct 290 ms 3696 KB Output is correct
13 Correct 293 ms 4972 KB Output is correct
14 Correct 317 ms 3820 KB Output is correct
15 Correct 332 ms 4972 KB Output is correct
16 Correct 343 ms 4588 KB Output is correct
17 Correct 354 ms 4716 KB Output is correct
18 Correct 386 ms 5680 KB Output is correct
19 Correct 351 ms 4588 KB Output is correct
20 Correct 425 ms 5740 KB Output is correct