제출 #1039516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1039516		Minbaev	거래 (IZhO13_trading)	C++17	100 / 100	168 ms	36180 KiB

trading

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
 
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define s second
#define int long long
#define pii pair<int,int>
 
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
 tree_order_statistics_node_update> ordered_set;
 
const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;

int binpow(int a, int b){
	if(b == 0)return 1;
	if(b % 2 == 0){
		int c = binpow(a,b/2);
		return (c*c)%mod;
	}
	return (binpow(a,b-1)*a)%mod;
}

int divi(int a, int b){
	return (a*(binpow(b,mod-2)))%mod;
}

int n,m,k;
vector<array<int,3>>t(N*4);

void push(int tl, int tr, int v){
	if(t[v][2] == 0)return;
	
	if(tr != tl){
		if(t[v*2][2] == 0){
			t[v*2][2] = t[v][2];
			t[v*2][1] = (tr+tl)/2;
			t[v*2][0] = t[v][0];
		}
		else if(t[v*2][0] != 0){
			int val = t[v*2][1] - t[v*2][0] + t[v*2][2];
			int val2 = t[v*2][1] - t[v][0] + t[v][2];
			if(umax(val, val2)){
				t[v*2][2] = t[v][2];
				t[v*2][0] = t[v][0];
			}
		}
		
		if(t[v*2+1][2] == 0){
			t[v*2+1][2] = t[v][2];
			t[v*2+1][1] = tr;
			t[v*2+1][0] = t[v][0];
		}
		else if(t[v*2+1][0] != 0){
			int val = t[v*2+1][1] - t[v*2+1][0] + t[v*2+1][2];
			int val2 = t[v*2+1][1] - t[v][0] + t[v][2];
			if(umax(val, val2)){
				t[v*2+1][2] = t[v][2];
				t[v*2+1][0] = t[v][0];
			}
		}
	}
	
}

void update(int tl, int tr, int v, int l, int r, int val){
	if(r < tl || tr < l)return;
	
	if(l <= tl && tr <= r){
		if(t[v][1] == 0){
			t[v][1] = tr;
			t[v][0] = l;
			t[v][2] = val;
		}
		else{
			int sum = t[v][1] - t[v][0] + t[v][2];
			int val2 = tr-l+val;
			if(umax(sum,val2)){
				t[v][1] = tr;
				t[v][0] = l;
				t[v][2] = val;
			}
			//~ if(tl == tr && tr == 3){
				//~ cout << l << " " << val << "\n";
			//~ }
		}
		return;
	}
	
	int tm = (tl+tr)/2;
	update(tl,tm,v*2,l,r,val);
	update(tm+1,tr,v*2+1,l,r,val);	
}

int get(int tl, int tr, int v, int pos){
	push(tl, tr, v);
	
	if(pos == tl && pos == tr){
		return (t[v][1]-t[v][0]+t[v][2]);
	}
	int tm = (tl+tr)/2;
	
	if(pos <= tm)
		return get(tl,tm,v*2,pos);
	else
		return get(tm+1,tr,v*2+1,pos);
}

void solve(){
	
	cin >> n >> m;
	
	while(m--){
		int a,b,c;
		cin >> a >> b >> c;
		//~ cout << "\n";
		update(1,n,1,a,b,c);
	}
	//~ cout << "\n";
	
	for(int i = 1;i<=n;i++){
		cout << get(1,n,1,i) << " ";
	}
	
}
 /*
5 4
1 2 1
2 3 3
3 4 5
4 5 7
 */
 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();
 
}
 

• Subtask 1: 100 / 100