제출 #416459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416459		alishahali1382	Food Court (JOI21_foodcourt)	C++14	100 / 100	801 ms	64772 KiB

foodcourt

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250010, LOG=18;

struct Fenwick{
	ll fen[MAXN];
	inline void add(int pos, ll val){
		for (; pos<MAXN; pos+=pos&-pos) fen[pos]+=val;
	}
	inline ll get(int pos){
		ll res=0;
		for (; pos; pos-=pos&-pos) res+=fen[pos];
		return res;
	}
	int BS(ll val){
		int res=0;
		for (int i=LOG-1; ~i; i--)
			if (res+(1<<i)<MAXN && fen[res+(1<<i)]<=val) val-=fen[res+=(1<<i)];
		return res+1;
	}
} fen1, fen2;
struct Segment{
	pll seg[MAXN<<2];
	ll lazy[MAXN<<2];
	Segment(){
		seg[0]={INF, 0};
	}
	pll Build(int id, int tl, int tr){
		if (tr-tl==1) return seg[id]={0, -tl};
		int mid=(tl+tr)>>1;
		return seg[id]=min(Build(id<<1, tl, mid), Build(id<<1 | 1, mid, tr));
	}
	inline void add_lazy(int id, ll val){
		seg[id].first+=val;
		lazy[id]+=val;
	}
	inline void shift(int id){
		if (lazy[id]){
			add_lazy(id<<1, lazy[id]);
			add_lazy(id<<1 | 1, lazy[id]);
			lazy[id]=0;
		}
	}
	void Add(int id, int tl, int tr, int l, int r, ll val){
		if (r<=tl || tr<=l) return ;
		if (l<=tl && tr<=r){
			add_lazy(id, val);
			return ;
		}
		shift(id);
		int mid=(tl+tr)>>1;
		Add(id<<1, tl, mid, l, r, val);
		Add(id<<1 | 1, mid, tr, l, r, val);
		seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
	}
	pll Get(int id, int tl, int tr, int l, int r){
		if (r<=tl || tr<=l) return seg[0];
		if (l<=tl && tr<=r) return seg[id];
		shift(id);
		int mid=(tl+tr)>>1;
		return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
	}
} seg;

int n, m, k, u, v, x, y, t, a, b;
int T[MAXN], A[MAXN], B[MAXN], C[MAXN], ans[MAXN];
ll K[MAXN];
vector<int> Q1[MAXN], Q2[MAXN], Q3[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>m;
	for (int i=1; i<=m; i++){
		cin>>T[i];
		if (T[i]<=2){
			cin>>A[i]>>B[i];
			Q1[A[i]].pb(i);
			Q2[B[i]].pb(i);
			if (T[i]==1) cin>>C[i];
			cin>>K[i];
		}
		else{
			cin>>A[i]>>K[i];
			Q3[A[i]].pb(i);
		}
	}
	seg.Build(1, 1, m+1);
	for (int i=1; i<=n; i++){
		for (int id:Q1[i]){
			int z=(T[id]==1?1:-1);
			seg.Add(1, 1, m+1, id, m+1, z*K[id]);
			if (T[id]==1) fen1.add(id, K[id]);
			if (T[id]==2) fen2.add(id, K[id]);
		}
		for (int id:Q3[i]){
			pll p=seg.Get(1, 1, m+1, 1, id+1);
			int l=(p.first<=0?-p.second:0)+1;
			if (l>id){
				ans[id]=0;
				continue ;
			}
//			debug(l)
			ll pos=fen1.get(id)-fen1.get(l-1);
			ll neg=fen2.get(id)-fen2.get(l-1);
			if (pos-neg<K[id]){
				ans[id]=0;
				continue ;
			}
			int res=fen1.BS(fen1.get(l-1) + neg + K[id]-1);
//			debug2(neg, pos)
			ans[id]=C[res];
//			debug2(id, ans[id])
		}
		for (int id:Q2[i]){
			int z=(T[id]==1?1:-1);
			seg.Add(1, 1, m+1, id, m+1, -z*K[id]);
			if (T[id]==1) fen1.add(id, -K[id]);
			if (T[id]==2) fen2.add(id, -K[id]);
		}
	}
	for (int i=1; i<=m; i++) if (T[i]==3) cout<<ans[i]<<"\n";
	
	return 0;
}
/*
1 0 5
1 1 1 1 1
1 1 1 4 1
2 1 1 1
1 1 1 2 1
3 1 1

*/

• 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