제출 #1257476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257476		ilhan_arda	Food Court (JOI21_foodcourt)	C++20	100 / 100	849 ms	86220 KiB

foodcourt

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int inf = 1e18;
const int mod = 1e9+7;

#ifdef ONLINE_JUDGE
template<typename... Args>
inline void debug(const Args&... args){
    return void("59");
}
#else
inline void debug(){cerr<<endl;}
template<typename... Args>
inline void debug(const Args&... args){
    ((cerr<<args<<' '),...)<<endl;
}
#endif
struct SegmentTree{
	//~ int a[1000005] = {0};
	int ST1[1000005] = {0}, ST2[1000005] = {0};
	ii ST3[1000005] = {{0, 0}};
	int lazy[1000005] = {0};
	SegmentTree(){}
	
	void push(int ind, int l, int r){ //min icin
		if(l!=r){
			lazy[ind*2] += lazy[ind]; 
			lazy[ind*2+1] += lazy[ind];
		}
		ST3[ind].fi += lazy[ind];
		lazy[ind] = 0;
	}
	void build3(int ind, int l, int r){
		if(l==r){
			ST3[ind].se = l;
			return;
		}
		int m = (l+r)/2;
		build3(ind*2, l, m);
		build3(ind*2+1, m+1, r);
		ST3[ind].se = ST3[ind*2].se;
	}
	void update1(int ind, int l, int r, int u, int v){ //ekleme
		if(l>u || r<u)return;
		if(l == r){
			ST1[ind] += v;
			return;
		}
		int m = (l+r)/2;
		update1(ind*2, l, m, u, v);
		update1(ind*2+1, m+1, r, u, v);
		ST1[ind] = ST1[ind*2] + ST1[ind*2+1];
	}
	void update2(int ind, int l, int r, int u, int v){ //cikarma
		if(l>u || r<u)return;
		if(l == r){
			ST2[ind] += v;
			return;
		}
		int m = (l+r)/2;
		update2(ind*2, l, m, u, v);
		update2(ind*2+1, m+1, r, u, v);
		ST2[ind] = ST2[ind*2] + ST2[ind*2+1];
	}
	void update3(int ind, int l, int r, int s, int f, int v){
		push(ind, l, r);
		if(l>f || r<s)return;
		if(l>=s && r<=f){
			lazy[ind] += v;
			push(ind, l, r);
			return;
		}
		int m = (l+r)/2;
		update3(ind*2, l, m, s, f, v);
		update3(ind*2+1, m+1, r, s, f, v);
		//~ ST3[ind].fi = min(ST3[ind*2].fi, ST3[ind*2+1].fi);
		ST3[ind] = ST3[ind*2].fi<ST3[ind*2+1].fi ? ST3[ind*2] : ST3[ind*2+1];
	}
	
	int query1(int ind, int l, int r, int s, int f){
		if(l>f || r<s)return 0;
		if(l>=s && r<=f)return ST1[ind];
		int m = (l+r)/2;
		return query1(ind*2, l, m, s, f) + query1(ind*2+1, m+1, r, s, f);
	}
	int walk(int ind, int l, int r, int cur, int x){ 
		if(l==r){
			if(x>cur+ST1[ind]){
				return -1;
			}
			return l;
		}
		int m = (l+r)/2;
		if(cur + ST1[ind*2] >= x){
			return walk(ind*2, l, m, cur, x);
		}
		else{
			return walk(ind*2+1, m+1, r, cur + ST1[ind*2], x);
		}
	}
	
	int query2(int ind, int l, int r, int s, int f){
		if(l>f || r<s)return 0;
		if(l>=s && r<=f)return ST2[ind];
		int m = (l+r)/2;
		return query2(ind*2, l, m, s, f) + query2(ind*2+1, m+1, r, s, f);
	}
	ii query3(int ind, int l, int r, int s, int f){
		push(ind, l, r);
		if(l>f || r<s)return {inf, -1};
		if(l>=s && r<=f)return ST3[ind];
		int m = (l+r)/2;
		ii t1 = query3(ind*2, l, m, s, f);
		ii t2 = query3(ind*2+1, m+1, r, s, f);
		return t1<t2 ? t1 : t2;
	}
};

int n, m, q, cnt, sorgucnt;
vector<array<int, 4>> inp;
set<array<int, 4>> st;
//~ set<array<int, 4>> inp2;
vector<vector<iii>> qinp;
vector<int> ans;
int32_t main(){
	fast;
	cin>>n>>m>>q;
	SegmentTree* ST = new SegmentTree();
	qinp.assign(n+5, vector<iii>());
	inp.pb(array<int, 4>());
	while(q--){
		int x;
		cin>>x;
		if(x == 1){
			cnt++;
			int l, r, c, k;
			cin>>l>>r>>c>>k;
			inp.pb({l, r, k, c});
			st.insert({l, cnt, k, 1});
			st.insert({r+1, cnt, -k, 1});
		}
		else if(x == 2){
			cnt++;
			int l, r, k;
			cin>>l>>r>>k;
			inp.pb({l, r, k, -1});
			st.insert({l, cnt, -k, -1});
			st.insert({r+1, cnt, k, -1});
		}
		else{
			sorgucnt ++;
			int a, b;
			cin>>a>>b;
			qinp[a].pb({cnt, b, sorgucnt}); //a dukkanina cnt update'ten sonra b queryisi geldi
		}
	}
	ST->build3(1, 1, cnt);
	ans.assign(sorgucnt+5, -1);
	//~ cerr<<cnt<<endl;
	//~ cerr<<sorgucnt<<endl;
	auto it = st.begin();
	for(int i=1;i<=n;i++){
		//~ cerr<<" a "<<i<<endl;
		while(it != st.end() && (*it)[0]<=i){
			//~ cerr<<"it"<<endl;
			//~ for(int j=0;j<=3;j++){
				//~ cerr<<(*it)[j]<<" .it. "<<i<<endl;
			//~ }cerr<<endl;
			if((*it)[3] == 1){
				ST->update1(1, 1, cnt, (*it)[1], (*it)[2]);
				ST->update3(1, 1, cnt, (*it)[1], cnt, (*it)[2]);
			}
			else{
				ST->update2(1, 1, cnt, (*it)[1], (*it)[2]);
				ST->update3(1, 1, cnt, (*it)[1], cnt, (*it)[2]);
			}
			it++;
		}
		//~ cerr<<"b"<<endl;
		for(int j=0;j<(ll)qinp[i].size();j++){
			//~ int ind = qinp[i][j].fi, k = qinp[i][j].se;
			int ind, k, sorguind;
			tie(ind, k, sorguind) = qinp[i][j];
			int mn, mnind;
			if(ind>1)tie(mn, mnind) = ST->query3(1, 1, cnt, 1, ind-1);
			else mn = 0, mnind = 0;
			if(mn > 0)mnind = 0;
			int negval = ST->query2(1, 1, cnt, mnind+1, ind);
			int sira = (mnind > 0 ? ST->query1(1, 1, cnt, 1, mnind) : 0) - negval + k;
			int qind = ST->walk(1, 1, cnt, 0, sira); 
			//~ cerr<<i<<" .i. "<<ind<<" .ind. "<<k<<" .k. "<<mn<<" .mn. "<<mnind<<" .mnind. "<<ST->query1(1, 1, cnt, 1, mnind)<<" .mnind'den once. "<<negval<<" .negval. "<<sira<<" .sira. "<<qind<<" .qind. "<<endl;
			//~ if(qind == -1 || qind > ind)cerr<<0<<endl;
			//~ else cerr<<inp[qind][3]<<endl;
			
			if(qind == -1 || qind > ind)ans[sorguind] = 0;
			else ans[sorguind] = inp[qind][3];
		}
	}
	//~ cout<<sorgucnt<<" .sorgucnt. "<<endl;
	for(int i=1;i<=sorgucnt;i++){
		cout<<ans[i]<<endl;
	}
}
//~ 1 2 8
//~ 1 1 1 2 3
//~ 1 1 1 1 2
//~ 2 1 1 2
//~ 3 1 1
//~ 3 1 2
//~ 2 1 1 5 
//~ 3 1 1
//~ 3 1 2

• 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