Submission #953019

#	Time	Username	Problem	Language	Result	Execution time	Memory
953019		WonderfulWhale	Food Court (JOI21_foodcourt)	C++17	100 / 100	939 ms	176532 KiB

foodcourt

// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
using namespace std;

#define INT __int128
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll __int128

const int INF = 1e17;

const int MAXN = 250'009;

namespace special {

const int MAXN = 500001;  // 1-based

int N = 400000;
ll A[MAXN];


struct Node {
	ll sum;   // Sum tag
	ll max1;  // Max value
	ll max2;  // Second Max value
	ll maxc;  // Max value count
	ll min1;  // Min value
	ll min2;  // Second Min value
	ll minc;  // Min value count
	ll lazy;  // Lazy tag
} T[MAXN * 4];

void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;
	// cerr << "check: " << (int)T[t].sum << "\n";

	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}

	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}

void push_add(int t, int tl, int tr, ll v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -INF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != INF) { T[t].min2 += v; }
	T[t].lazy += v;
}

// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}

void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;

	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}

void build(int t = 1, int tl = 0, int tr = N - 1) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -INF;
		T[t].min2 = INF;
		return;
	}

	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_add(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	// cerr << "change!!!\n";
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_add(l, r, v, t << 1, tl, tm);
	update_add(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) +
	       query_sum(l, r, t << 1 | 1, tm + 1, tr);
}
}

struct SegTree {
	const static int T = 1<<20;
	int t[2*T];
	void update(int l, int r, int val) {
		// cerr << "we are for sure doing something\n";
		// cerr << "dane: "<< l << " " << r<< "\n";
		// cerr << val << "!!!\n";
		l+=T, r+=T;
		t[l]+=val;
		// cerr << "update: " << l << "\n";
		if(l!=r) {
			t[r]+=val;
			// cerr << "update: " << r << "\n";
		}
		// cerr << "start: "<< l << " " << r << "\n";
		while(l/2!=r/2) {
			// cerr << "i cyk\n";
			if(l%2==0) {
				t[l+1]+=val;
				// cerr << "update: " << l+1 << "\n";
			}
			if(r%2==1) {
				t[r-1]+=val;
				// cerr << "update: " << r-1 << "\n";
			}
			l/=2;
			r/=2;
			// cerr << "new: " << l << " " << r << "\n";
			// cerr << "polowki: " << l/2 << " " << r/2 << "\n";
		}
	}
	int query(int x) {
		// cerr << "query: " << x << "\n";
		x+=T;
		int ret = 0;
		while(x){ 
			// cerr << t[x] << " " << x <<" WOW\n";
			ret += t[x];
			x/=2;
		}
		return ret;
	}
} seg;

struct SegTree2 {
	const static int T = 1<<18;
	pii t[2*T];
	int lz[2*T];
	SegTree2() {
		for(int i=T;i<2*T;i++) {
			t[i] = {INF, i-T};
		}
		for(int i=T-1;i;i--) {
			t[i] = min(t[2*i], t[2*i+1]);
		}
	}
	void push(int v) {
		int l = 2*v, r = 2*v+1;
		t[l].st += lz[v];
		t[r].st += lz[v];
		lz[l] += lz[v];
		lz[r] += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int val, int tl=0, int tr=T-1, int v=1) {
		// if(v==1) cerr << "update: " << l << " " << r << " " << val << "\n";
		if(l>r) return;
		if(l==tl&&r==tr) {
			t[v].st += val;
			lz[v] += val;
			return;
		}
		push(v);
		int tm = (tl+tr)/2;
		update(l, min(r, tm), val, tl, tm, 2*v);
		update(max(tm+1, l), r, val, tm+1, tr, 2*v+1);
		t[v] = min(t[2*v], t[2*v+1]);
	}
	pii query(int l, int r, int tl=0, int tr=T-1, int v=1) {
		if(l>r) return make_pair(INF, -1);
		if(l==tl&&r==tr) {
			return t[v];
		}
		push(v);
		int tm = (tl+tr)/2;
		return min(query(l, min(r, tm), tl, tm, 2*v),
				query(max(tm+1, l), r, tm+1, tr, 2*v+1));
	}
} seg2;

vector<tuple<int, int, int, int>> Q;
int tab[MAXN];
int lim[MAXN];
pii info[MAXN];
int ans[MAXN];

int tmp[MAXN];
int del[MAXN];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<pii> zap;
	
	int n, m, q;
	cin >> n >> m >> q;
	int cnt = 0;
	int cnt3 = 0;
	special::build();
	for(int i=0;i<q;i++) {
		int type;
		cin >> type;
		if(type==1) {
			int l, r, c, k;
			cin >> l >> r >> k >> c;
			tab[cnt] = k;
			Q.pb({l, r, c, k});
			cnt++;
			seg.update(l, r, c);
			// cerr << "update: " << l << " " << r << " " << c << "\n";
			special::update_add(l, r, c);
			// cerr << "CHANGE \n";
			// cerr << l << " " << r << " " << c << " " << special::query_sum(0, 1000) << "\n";
			// for(int i=l;i<=r;i++) {
			// 	tmp[i] += c;
			// }
		}
		if(type==2) {
			int l, r, c;
			cin >> l >> r >> c;
			// seg.update(l, r, c);
			special::update_add(l, r, -c);
			special::update_chmax(l, r, 0);
			// for(int i=l;i<=r;i++) {
			// 	int val = min(c, tmp[i]);
			// 	tmp[i] -= val;
			// 	del[i] += val;
			// }
		}
		if(type==3) {
			int a, b;
			cin >> a >> b;
			// cerr << "QUERY : "<< a << "\n";
			// cerr << "query: " << a << " " << b << "\n";
			// b += seg.query(a);
			// cerr << "check: " << seg.query(a) << "\n";
			// cerr << "check2: " << (int)(special::query_sum(a, a)/INF) << (int)(special::query_sum(a, a)%INF) << "\n";
			int diff = seg.query(a)-special::query_sum(a, a);
			// b += del[a];
			b += diff;
			// cerr << del[a] << " " << diff << " test\n";
			// cerr << "we need: " << b << "\n";
			// cerr << "we can process: " << cnt << "\n";
			info[cnt3] = {cnt, b};
			zap.pb({a, cnt3++});
		}
	}
	// cerr << seg.query(106761) << " HAHA\n";
	sort(all(zap));
	for(int i=0;i<cnt3;i++) {
		int num = zap[i].nd;
		// cerr << "hm: " << info[num].nd << "\n";
		seg2.update(i, i, -INF+info[num].nd);
		pii X = seg2.query(i, i);
		// cerr << "just a quick check: " << X.st << " " << X.nd << "\n";
	}
	for(int i=0;i<cnt;i++) {
		auto [l, r, C, k] = Q[i];
		// cerr << "Now adding: " << l << " " << r << " " << C << " " << k << "\n";
		int s = -1;
		int e = cnt3;
		while(e-s>1) {
			int m = (e+s)/2;
			if(zap[m].st>=l) e = m;
			else s = m;
		}
		int S = e;
		s = -1, e = cnt3;
		while(e-s>1) {
			int m = (e+s)/2;
			if(zap[m].st<=r) s = m;
			else e = m;
		}
		int E = s;
		// cerr << "we will affect queries: "<< S << " " << E << "\n";
		seg2.update(S, E, -C);
		while(true) {
			pii x = seg2.query(0, cnt3-1);
			if(x.st>0) break;
			// cerr << "found: " << x.nd << " with new val: " << x.st << "\n";
			if(i<info[zap[x.nd].nd].st) ans[zap[x.nd].nd] = tab[i];
			seg2.update(x.nd, x.nd, INF);
		}
	}
	for(int i=0;i<cnt3;i++) {
		cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:338:7: warning: variable 'X' set but not used [-Wunused-but-set-variable]
  338 |   pii X = seg2.query(i, i);
      |       ^

• 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