Submission #301178

#	Time	Username	Problem	Language	Result	Execution time	Memory
301178		AMO5	Constellation 3 (JOI20_constellation3)	C++17	0 / 100	4 ms	5248 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ii pair<int,int>
#define fi first
#define se second

const int mxn = 2e5+5;
int n,m;
ll tree[mxn*4];
int h[mxn],pre[mxn],nxt[mxn];

struct star{
	int c,r;
	ll val;
	
	bool operator < (const star &rhs)const{
		return r>rhs.r;
	}
};

star stars[mxn];
vector<int>ind[mxn]; //keeping ind

ll query(int pos, int id, int le, int ri){
	if(le==ri){
		return tree[id];
	}
	int mid=(le+ri)>>1;
	ll res = 0ll;
	if(le<=pos&&pos<=ri)res+=tree[id];
	if(pos<=mid)res += query(pos,id*2,le,mid);
	else res+=query(pos,id*2+1,mid+1,ri);
	return res;
}

void upd(int x, int y, ll v, int id, int le, int ri){
	if(x>ri||le>y)return;
	if(x<=le&&ri<=y){
		tree[id]+=v;
		return;
	}
	int mid=(le+ri)>>1;
	upd(x,y,v,id*2,le,mid);
	upd(x,y,v,id*2+1,mid+1,ri);
	return;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>h[i];
		h[i]=n-h[i];
	}
	ll ans = 0ll;
	h[0]=h[n+1]=0;
	cin>>m;
	for(int i=0; i<m; i++){
		int c,r; ll v;
		cin>>c>>r>>v;
		ans += v;
		r = n-r+1;
		stars[i]={c,r,v};
	}
	sort(stars,stars+m);
	for(int i=0; i<m; i++)
		ind[stars[i].c].emplace_back(i);
	vector<int>h_ind;
	set<ii>ss;
	h_ind.push_back(n+1);
	ss.insert(ii(h[n+1],n+1));
	for(int i=n; i>=1; i--){
		while(!h_ind.empty()&&h[h_ind.back()]>=h[i]){
			ss.erase({h_ind.back(),h[h_ind.back()]});
			h_ind.pop_back();
		}
		/*
		cerr<<i<<": af \n";
		for(int j:h_ind)cerr<<j<<" ";
		cerr<<"\n";
		for(ii x:ss)cerr<<x.fi<<" "<<x.se<<"\n";
		cerr<<"\n";
		*/ 
		for(int j:ind[i]){
			auto it = ss.lower_bound({stars[j].r,-1});
			it = prev(it);
			//cerr<<j<<" "<<stars[j].r<<" "<<it->fi<<" "<<it->se<<"\n";
			nxt[j]=it->se-1;
			//cerr<<j<<" ... "<<nxt[j]<<"\n";
		}
		ss.emplace(h[i],i);
		h_ind.emplace_back(i);
	}
	ss=set<ii>();
	h_ind=vector<int>();
	h_ind.push_back(0);
	ss.insert(ii(h[0],0));
	for(int i=1; i<=n; i++){
		while(!h_ind.empty()&&h[h_ind.back()]>=h[i]){
			ss.erase({h_ind.back(),h[h_ind.back()]});
			h_ind.pop_back();
		}
		for(int j:ind[i]){
			auto it = ss.lower_bound({stars[j].r,-1});
			it=prev(it);
			pre[j]=it->se+1;
		}
		ss.emplace(h[i],i);
		h_ind.emplace_back(i);
	}
	/*
	for(int i=0; i<m; i++){
		cerr<<stars[i].c<<" "<<stars[i].r<<" "<<stars[i].val<<" "<<pre[i]<<" "<<nxt[i]<<"\n";
	}
	*/ 
	for(int i=0; i<m; i++){
		ll val = stars[i].val-query(stars[i].c,1,1,n);
		//cerr<<i<<" "<<stars[i].c<<": "<<val<<" "<<stars[i].val<<"\n";
		if(val>0){
			ans -= val;
			//cerr<<"upd "<<pre[i]<<" "<<nxt[i]<<"\n";
			upd(pre[i],nxt[i],val,1,1,n);
		}
	}
	cout<<ans<<endl;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65