제출 #1311543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311543		namhh	Food Court (JOI21_foodcourt)	C++20	100 / 100	555 ms	44248 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 250005;
int n,m,q,bits[N],st[4*N],lazy[4*N],lazymx[4*N],base[N],pos[N],pos2[N],l[N],r[N],ans[N],lim = 0,lim2 = 0;
vector<int>v[N];
struct query{
	int type,l,r,c,k;
};
query qr[N];
void update(int u, int val){
	while(u <= n){
		bits[u] += val;
		u += u & (-u);
	}
}
int get(int u){
	int sum = 0;
	while(u > 0){
		sum += bits[u];
		u -= u & (-u);
	}
	return sum;
}
void down(int id){
	if(lazy[id] != 0){
		st[2*id] += lazy[id];
		st[2*id+1] += lazy[id];
		lazy[2*id] += lazy[id];
		lazy[2*id+1] += lazy[id];
		if(lazymx[2*id] != -1) lazymx[2*id] += lazy[id];
		if(lazymx[2*id+1] != -1) lazymx[2*id+1] += lazy[id];
		lazy[id] = 0;
	}
	if(lazymx[id] != -1){
		st[2*id] = max(st[2*id],lazymx[id]);
		st[2*id+1] = max(st[2*id+1],lazymx[id]);
		lazymx[2*id] = max(lazymx[2*id],lazymx[id]);
		lazymx[2*id+1] = max(lazymx[2*id+1],lazymx[id]);
		lazymx[id] = -1;
	}
}
void add(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] += val;
		lazy[id] += val;
		if(lazymx[id] != -1) lazymx[id] += val;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	add(2*id,l,mid,u,v,val);
	add(2*id+1,mid+1,r,u,v,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] = max(st[id],val);
		lazymx[id] = max(lazymx[id],val);
		return;
	}
	down(id);
	int mid = (l+r)/2;
	update(2*id,l,mid,u,v,val);
	update(2*id+1,mid+1,r,u,v,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
int get(int id, int l, int r, int i){
	if(l == r) return st[id];
	int mid = (l+r)/2;
	down(id);
	if(i <= mid) return get(2*id,l,mid,i);
	return get(2*id+1,mid+1,r,i);
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i <= 4*n; i++) lazymx[i] = -1;
	for(int i = 1; i <= q; i++){
		cin >> qr[i].type >> qr[i].l >> qr[i].r;
		if(qr[i].type == 1){
			cin >> qr[i].c >> qr[i].k;
			++lim;
			pos[lim] = i;
			update(qr[i].l,qr[i].k);
		    update(qr[i].r+1,-qr[i].k);
		    add(1,1,n,qr[i].l,qr[i].r,qr[i].k);
		}
		if(qr[i].type == 2){
		    cin >> qr[i].k;
		    update(1,1,n,qr[i].l,qr[i].r,qr[i].k);
		    add(1,1,n,qr[i].l,qr[i].r,-qr[i].k);
		}
		if(qr[i].type == 3){
			++lim2;
		    l[lim2] = 1;
		    r[lim2] = lim;
		    pos2[lim2] = i;
		    base[lim2] = get(qr[i].l)-get(1,1,n,qr[i].l);
		}
	}
	while(true){
		int cnt = 0;
		for(int i = 1; i <= n; i++) bits[i] = 0;
		for(int i = 1; i <= lim; i++) v[i].clear();
		for(int i = 1; i <= lim2; i++){
			if(l[i] <= r[i]){
				cnt++;
				v[(l[i]+r[i])/2].push_back(i);
			}
		}
		if(cnt == 0) break;
		for(int i = 1; i <= lim; i++){
			int id = pos[i];
			update(qr[id].l,qr[id].k);
			update(qr[id].r+1,-qr[id].k);
			for(int qq: v[i]){
				int idd = pos2[qq];
				int val = get(qr[idd].l);
				if(val >= base[qq]+qr[idd].r){
					ans[qq] = qr[id].c;
					r[qq] = i-1;
				}
				else l[qq] = i+1;
			}
		}
	}
	for(int i = 1; i <= lim2; i++) cout << ans[i] << "\n";
}

• 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