제출 #528211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528211		fatemetmhr	푸드 코트 (JOI21_foodcourt)	C++17	0 / 100	529 ms	60208 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxnt = 1.2e6 + 10;
const int maxn5 = 3e5   + 10;
const ll  inf   = 1e18;

#define se  second
#define fi  first
#define all(x)  x.begin(), x.end()
#define pb  push_back



struct maxquery{
	ll a, b;
	maxquery(){
		a = 0;
		b = -inf;
	}
	maxquery(ll aa, ll bb){
		a = aa;
		b = bb;
	}
	inline void emp(){
		a = 0;
		b = -inf;
	}
} seg[maxnt];

int ty[maxn5], l[maxn5], r[maxn5];
ll c[maxn5], k[maxn5], lazy[maxnt], ext[maxnt];
vector <pair<ll, ll>> av[maxn5];
pair <ll, ll> mx[maxnt];
ll tmp[maxn5];
int out[maxn5], pt[maxn5];

inline maxquery operator +(maxquery a, maxquery b){
	maxquery ret;
	ret.a = a.a + b.a;
	ret.b = max(a.b + b.a, b.b);
	return ret;
}

inline void shift(int v){
	seg[v * 2] = seg[v * 2] + seg[v];
	seg[v * 2 + 1] = seg[v * 2 + 1] + seg[v];
	seg[v].emp();
	return;
}

inline void add(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		ext[v] += val;
		return;
	}
	int mid = (l + r) >> 1;
	add(l, mid, lq, rq, val, v * 2);
	add(mid, r, lq, rq, val, v * 2 + 1);
	return;
}

inline ll get(int l, int r, int ind, int v){
	if(r - l == 1)
		return ext[v];
	int mid = (l + r) >> 1;
	if(ind < mid)
		return get(l, mid, ind, v * 2) + ext[v];
	return get(mid, r, ind, v * 2 + 1) + ext[v];
}

inline void maxmos(int l, int r, int lq, int rq, ll a, ll b, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		seg[v] = seg[v] + maxquery(a, b);
		return;
	}
	int mid = (l + r) >> 1; shift(v);
	maxmos(l, mid, lq, rq, a, b, v * 2);
	maxmos(mid, r, lq, rq, a, b, v * 2 + 1);
	return;
}

inline ll getmm(int l, int r, int ind, int v){
	if(r - l == 1){
		return max(seg[v].b, seg[v].a);
	}
	int mid = (l + r) >> 1; shift(v);
	if(ind < mid)
		return getmm(l, mid, ind, v * 2);
	return getmm(mid, r, ind, v * 2 + 1);
}

inline void build(int l, int r, int v){
	if(r - l == 1){
		mx[v] = {tmp[l], l};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	return;
}

inline void adds(int l, int r, int lq, int rq, ll val, int v){
	if(rq <= l || r <= lq)
		return;
	if(lq <= l && r <= rq){
		lazy[v] += val;
		mx[v].fi += val;
		return;
	}
	int mid = (l + r) >> 1;
	adds(l, mid, lq, rq, val, v * 2);
	adds(mid, r, lq, rq, val, v * 2 + 1);
	mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	mx[v].fi += lazy[v];
	return;
}


int main(){
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < q; i++){
		cin >> ty[i];
		if(ty[i] == 1){
			cin >> l[i] >> r[i] >> c[i] >> k[i];
			maxmos(0, n, --l[i], r[i]--, k[i], -inf, 1);
			add(0, n, l[i], r[i] + 1, k[i], 1);
		}
		if(ty[i] == 2){
			cin >> l[i] >> r[i] >> k[i];
			maxmos(0, n, --l[i], r[i]--, -k[i], 0, 1);
		}
		if(ty[i] == 3){
			cin >> c[i] >> k[i];
			ll ex = get(0, n, --c[i], 1);
			//cout << "ok " << ex << endl;
			ll exx = getmm(0, n, c[i], 1); 
			//cout << "and " << exx << endl;
			ex -= exx;
			av[c[i]].pb({k[i] + ex, i});
		}
	}
	
	
	for(int i = 0; i < n; i++){
		sort(all(av[i]));
		if(av[i].size()){
			tmp[i] = -av[i][0].fi;
			//cout << i << ' ' << -av[i][0].fi << endl;
		}
		else
			tmp[i] = -inf;
	}
	
	build(0, n, 1);
	
	for(int i = 0; i < q; i++){
		if(ty[i] == 1){
			adds(0, n, l[i], r[i] + 1, k[i], 1);
		}
		while(mx[1].fi >= 0){
			int id = mx[1].se;
			//cout << "ok for " << id << endl;
			if(av[id][pt[id]].se >= i)
				out[av[id][pt[id]].se] = c[i];
			pt[id]++;
			adds(0, n, id, id + 1, pt[id] == av[id].size() ? -inf : av[id][pt[id]].fi - av[id][pt[id]].fi, 1);
		}
	}
	
	for(int i = 0; i < q; i++)
		if(ty[i] == 3)
			cout << out[i] << '\n';
}

/*
3 5 3
1 2 3 5 2
1 1 2 2 4
3 2 3
*/

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:176:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |    adds(0, n, id, id + 1, pt[id] == av[id].size() ? -inf : av[id][pt[id]].fi - av[id][pt[id]].fi, 1);
      |                           ~~~~~~~^~~~~~~~~~~~~~~~

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