oj.uz

Submission #344512

# Submission time Handle Problem Language Result Execution time Memory
344512 2021-01-06T03:53:39 Z nandonathaniel Trading (IZhO13_trading) C++14
100 / 100
 742 ms 44640 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 10 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 12 ms 14572 KB Output is correct
6 Correct 13 ms 14700 KB Output is correct
7 Correct 358 ms 30432 KB Output is correct
8 Correct 370 ms 31184 KB Output is correct
9 Correct 387 ms 30800 KB Output is correct
10 Correct 397 ms 30544 KB Output is correct
11 Correct 490 ms 32544 KB Output is correct
12 Correct 470 ms 31984 KB Output is correct
13 Correct 503 ms 33484 KB Output is correct
14 Correct 539 ms 32772 KB Output is correct
15 Correct 573 ms 33760 KB Output is correct
16 Correct 648 ms 34912 KB Output is correct
17 Correct 562 ms 33884 KB Output is correct
18 Correct 609 ms 41304 KB Output is correct
19 Correct 597 ms 34960 KB Output is correct
20 Correct 742 ms 44640 KB Output is correct