oj.uz

Submission #344508

# Submission time Handle Problem Language Result Execution time Memory
344508 2021-01-06T03:51:51 Z nandonathaniel Trading (IZhO13_trading) C++14
100 / 100
 746 ms 50896 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=300005;

vector<pii> masuk[MAXN];
vector<LL> keluar[MAXN];

LL tree[4*MAXN],lazy[4*MAXN];

void updatenode(LL now,LL val){
	tree[now]+=val;
	lazy[now]+=val;
}

void pushdown(LL now){
	updatenode(2*now,lazy[now]);
	updatenode(2*now+1,lazy[now]);
	lazy[now]=0;
}

void update(LL now,LL L,LL R,LL x,LL y,LL val){
	if(L>=x && R<=y){
		updatenode(now,val);
		return;
	}
	if(L>y || R<x)return;
	LL mid=(L+R)/2;
	pushdown(now);
	update(2*now,L,mid,x,y,val);
	update(2*now+1,mid+1,R,x,y,val);
	tree[now]=max(tree[2*now],tree[2*now+1]);
}

LL query(LL now,LL L,LL R,LL x,LL y){
	if(L>=x && R<=y)return tree[now];
	if(L>y || R<x)return -2e9;
	LL mid=(L+R)/2;
	pushdown(now);
	return max(query(2*now,L,mid,x,y),query(2*now+1,mid+1,R,x,y));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	LL n,m,l,r,x;
	cin >> n >> m;
	for(LL i=1;i<=m;i++){
		cin >> l >> r >> x;
		masuk[l].push_back({i,x});
		keluar[r+1].push_back(i);
		update(1,1,m,i,i,-2e9);
	}
	for(LL i=1;i<=n;i++){
		for(auto isi : keluar[i])update(1,1,m,isi,isi,-2e9);
		for(auto isi : masuk[i])update(1,1,m,isi.first,isi.first,2e9-i+isi.second);
		update(1,1,m,1,m,1);
		LL brp=query(1,1,m,1,m);
		if(brp<1)brp=0;
		cout << brp;
		if(i<n)cout << " ";
	}
	cout << '\n';
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14572 KB Output is correct
5 Correct 14 ms 14572 KB Output is correct
6 Correct 13 ms 14700 KB Output is correct
7 Correct 333 ms 32992 KB Output is correct
8 Correct 378 ms 34128 KB Output is correct
9 Correct 393 ms 33872 KB Output is correct
10 Correct 417 ms 33916 KB Output is correct
11 Correct 435 ms 36056 KB Output is correct
12 Correct 475 ms 35796 KB Output is correct
13 Correct 509 ms 37324 KB Output is correct
14 Correct 502 ms 36936 KB Output is correct
15 Correct 601 ms 38236 KB Output is correct
16 Correct 647 ms 39684 KB Output is correct
17 Correct 575 ms 38704 KB Output is correct
18 Correct 623 ms 46492 KB Output is correct
19 Correct 643 ms 39764 KB Output is correct
20 Correct 746 ms 50896 KB Output is correct