Submission #1256443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256443		PieArmy	Food Court (JOI21_foodcourt)	C++20	100 / 100	610 ms	116996 KiB

foodcourt

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

struct Seg{
	#define mid ((left+right)>>1)
	#define sol node*2,left,mid
	#define sag node*2+1,mid+1,right
	int n;
	vector<ll>tree;
	vector<pair<ll,int>>pref;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=0;
			pref[node]={0,-left};
			return;
		}
		build(sol);
		build(sag);
		tree[node]=tree[node*2]+tree[node*2+1];
		pref[node]=min(pref[node*2],{tree[node*2]+pref[node*2+1].fr,pref[node*2+1].sc});
	}
	void init(int N){
		n=N;
		tree.resize(n<<2);
		pref.resize(n<<2);
		build();
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			pref[node]={tree[node]=r,-left};
			return;
		}
		if(l>mid)up(sag);
		else up(sol);
		tree[node]=tree[node*2]+tree[node*2+1];
		pref[node]=min(pref[node*2],{tree[node*2]+pref[node*2+1].fr,pref[node*2+1].sc});
	}
	void update(int tar,int val){
		l=tar;r=val;
		up();
	}
	pair<ll,pair<ll,int>> qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return {tree[node],pref[node]};
		if(left>r||right<l)return {0,{1e9+1,1}};
		pair<ll,pair<ll,int>>res,a=qu(sol),b=qu(sag);
		res.fr=a.fr+b.fr;
		res.sc=min(a.sc,{a.fr+b.sc.fr,b.sc.sc});
		return res;
	}
	pair<ll,pair<ll,int>> query(int left,int right){
		l=left;
		r=right;
		if(l==-1||r==-1||l>r)return {0,{1e9+1,1}};
		return qu();
	}
	int walk(ll k,int node=1,int left=0,int right=-1){
		if(k==0)return n;
		if(right==-1)right=n-1;
		if(tree[node]<k)return n;
		if(left==right)return left;
		if(tree[node*2]>=k)return walk(k,sol);
		k-=tree[node*2];
		return walk(k,sag);
	}
	#undef mid
};

int n,m,q;
vector<ll>query[250023];
vector<int>ekle[250023],cikar[250023],sor[250023];
ll ans[250023];
Seg pos,neg,both;

int main(){
	ios_base::sync_with_stdio(23-23);cin.tie(0);
	cin>>n>>m>>q;
	for(int i=0;i<q;i++){
		int t;cin>>t;
		vector<ll>&v=query[i];
		if(t==1){
			v.resize(4);
			cin>>v[0]>>v[1]>>v[2]>>v[3];
			ekle[v[0]].pb(i);
			cikar[v[1]+1].pb(i);
		}
		else if(t==2){
			v.resize(3);
			cin>>v[0]>>v[1]>>v[2];
			v[2]*=-1;
			ekle[v[0]].pb(i);
			cikar[v[1]+1].pb(i);
		}
		else{
			v.resize(2);
			cin>>v[0]>>v[1];
			sor[v[0]].pb(i);
		}
	}
	query[q].resize(3,0);
	pos.init(q);
	neg.init(q);
	both.init(q);
	for(int i=1;i<=n;i++){
		for(int x:ekle[i]){
			both.update(x,query[x].back());
			if(query[x].back()>0){
				pos.update(x,query[x].back());
			}
			else neg.update(x,query[x].back());
		}
		for(int x:cikar[i]){
			both.update(x,0);
			if(query[x].back()>0){
				pos.update(x,0);
			}
			else neg.update(x,0);
		}
		for(int x:sor[i]){
			pair<ll,int>mn=both.query(0,x).sc;
			mn.sc*=-1;
			if(mn.fr>0)mn.sc=-1;
			ll w=neg.query(mn.sc+1,x).fr;
			ll ek=pos.query(0,mn.sc).fr;
			int tar=pos.walk(query[x].back()-w+ek);
			if(tar<x)ans[x]=query[tar][2];
		}
	}
	for(int i=0;i<q;i++){
		if(query[i].size()==2)cout<<ans[i]<<endl;
	}
}

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