Submission #1010232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010232		pcc	Food Court (JOI21_foodcourt)	C++17	24 / 100	216 ms	53960 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll mxn = 250005;
#define tlll tuple<ll,ll,ll>
#define pll pair<ll,ll>
#define fs first
#define sc second


#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
	struct node{
		ll in,out,debt;
		node(ll ii = 0,ll oo = 0,ll dd = 0){
			in = ii,out = oo,debt = dd;
		}
	};
	node seg[mxn*4];
	node addtag(node u,node d){
		ll dif = min(u.debt,d.in);
		d.in -= dif;
		u.debt -= dif;
		d.out = u.out+d.out+dif;
		d.debt = d.debt+u.debt;
		d.in = d.in+u.in;
		return d;
	}
	void push(int now,int l,int r){
		seg[ls] = addtag(seg[now],seg[ls]);
		seg[rs] = addtag(seg[now],seg[rs]);
		seg[now].in = seg[now].out = seg[now].debt = 0;
		return;
	}
	void add(int now,int l,int r,int s,int e,ll v){
		if(l>=s&&e>=r){
			seg[now].in += v;
			return;
		}
		push(now,l,r);
		if(mid>=s)add(ls,l,mid,s,e,v);
		if(mid<e)add(rs,mid+1,r,s,e,v);
		return;
	}
	void del(int now,int l,int r,int s,int e,ll v){
		if(l>=s&&e>=r){
			seg[now] = addtag(node(0,0,v),seg[now]);
			return;
		}
		push(now,l,r);
		if(mid>=s)del(ls,l,mid,s,e,v);
		if(mid<e)del(rs,mid+1,r,s,e,v);
	}
	int getval(int now,int l,int r,int p,ll cnt){
		if(l == r){
			if(seg[now].in<cnt)return -1;
			else return seg[now].out+cnt;
		}
		push(now,l,r);
		if(mid>=p)return getval(ls,l,mid,p,cnt);
		else return getval(rs,mid+1,r,p,cnt);
	}
};

struct SEG2{
	ll seg[mxn*4];
	void modify(int now,int l,int r,int p,ll v){
		if(l == r){
			seg[now] += v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = seg[ls]+seg[rs];
	}
	ll getbig(int now,int l,int r,ll tar){
		if(l == r)return l;
		if(seg[ls]>=tar)return getbig(ls,l,mid,tar);
		else return getbig(rs,mid+1,r,tar-seg[ls]);
	}
};

#undef ls
#undef rs
#undef mid

SEG1 seg1;
SEG2 seg2;
ll N,M,Q;
int col[mxn];
vector<pll> req[mxn];
int ans[mxn];
vector<pll> op[mxn];
vector<int> askid;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	for(int i = 1;i<=Q;i++){
		int t;
		cin>>t;
		if(t == 1){
			ll l,r,c,k;
			cin>>l>>r>>c>>k;
			op[l].push_back(pll(i,k));
			op[r+1].push_back(pll(i,-k));
			col[i] = c;
			seg1.add(0,1,N,l,r,k);
		}
		else if(t == 2){
			ll l,r,k;
			cin>>l>>r>>k;
			seg1.del(0,1,N,l,r,k);
		}
		else{
			ll a,b;
			cin>>a>>b;
			askid.push_back(i);
			auto tmp = seg1.getval(0,1,N,a,b);
			if(tmp == -1)ans[i] = -1;
			else req[a].push_back(pll(i,tmp));
		}
	}
	for(int i = 1;i<=N;i++){
		for(auto &j:op[i]){
			seg2.modify(0,1,Q,j.fs,j.sc);
		}
		for(auto &j:req[i]){
			ans[j.fs] = col[seg2.getbig(0,1,Q,j.sc)];
		}
	}
	for(auto &i:askid)cout<<max(ans[i],0)<<'\n';
	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 15 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11