oj.uz

Submission #952989

# Submission time Handle Problem Language Result Execution time Memory
952989 2024-03-25T09:21:11 Z WonderfulWhale Food Court (JOI21_foodcourt) C++17
14 / 100
 1000 ms 26576 KB 
#include<bits/stdc++.h>
using namespace std;

#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()

const int INF = 1e18;

const int MAXN = 250'009;

struct SegTree {
	const static int T = 1<<18;
	int t[2*T];
	void update(int l, int r, int val) {
		l+=T, r+=T;
		t[l]+=val;
		if(l!=r) t[r]+=val;
		if(l/2!=r/2) {
			if(l%2==0) t[l+1]+=val;
			if(r%2==1) t[r-1]+=val;
			l/=2;
			r/=2;
		}
	}
	int query(int x) {
		x+=T;
		int ret = 0;
		while(x){ 
			ret += t[x];
			x/=2;
		}
		return ret;
	}
} seg, 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] = {1e18, 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(1e18, -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;
	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++;
			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);
			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 << " " << b << "\n";
			// b += seg.query(a);
			b += del[a];
			// cerr << "we need: " << b << "\n";
			// cerr << "we can process: " << cnt << "\n";
			info[cnt3] = {cnt, b};
			zap.pb({a, cnt3++});
		}
	}
	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, 1e18);
		}
	}
	for(int i=0;i<cnt3;i++) {
		cout << ans[i] << "\n";
	}
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22876 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 21084 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 7 ms 23132 KB Output is correct
12 Correct 6 ms 23128 KB Output is correct
13 Correct 6 ms 21104 KB Output is correct
14 Correct 9 ms 23132 KB Output is correct
15 Correct 6 ms 20828 KB Output is correct
16 Correct 8 ms 23132 KB Output is correct
17 Correct 5 ms 23092 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23128 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22876 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 21084 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 7 ms 23132 KB Output is correct
12 Correct 6 ms 23128 KB Output is correct
13 Correct 6 ms 21104 KB Output is correct
14 Correct 9 ms 23132 KB Output is correct
15 Correct 6 ms 20828 KB Output is correct
16 Correct 8 ms 23132 KB Output is correct
17 Correct 5 ms 23092 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23128 KB Output is correct
21 Correct 6 ms 23132 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct
23 Correct 6 ms 21088 KB Output is correct
24 Correct 6 ms 21084 KB Output is correct
25 Correct 5 ms 23020 KB Output is correct
26 Correct 4 ms 23020 KB Output is correct
27 Correct 6 ms 23132 KB Output is correct
28 Correct 6 ms 23132 KB Output is correct
29 Correct 6 ms 23108 KB Output is correct
30 Correct 7 ms 21096 KB Output is correct
31 Correct 8 ms 23132 KB Output is correct
32 Correct 6 ms 21084 KB Output is correct
33 Correct 6 ms 21084 KB Output is correct
34 Correct 8 ms 23132 KB Output is correct
35 Correct 7 ms 23132 KB Output is correct
36 Correct 7 ms 21084 KB Output is correct
37 Correct 4 ms 23132 KB Output is correct
38 Correct 5 ms 23140 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 22552 KB Output is correct
2 Correct 369 ms 25936 KB Output is correct
3 Correct 509 ms 22476 KB Output is correct
4 Correct 485 ms 24276 KB Output is correct
5 Correct 414 ms 25928 KB Output is correct
6 Correct 396 ms 26056 KB Output is correct
7 Correct 36 ms 23244 KB Output is correct
8 Correct 38 ms 22736 KB Output is correct
9 Correct 786 ms 24492 KB Output is correct
10 Correct 774 ms 24752 KB Output is correct
11 Correct 829 ms 23856 KB Output is correct
12 Correct 794 ms 24084 KB Output is correct
13 Correct 160 ms 25928 KB Output is correct
14 Correct 237 ms 24904 KB Output is correct
15 Correct 63 ms 26336 KB Output is correct
16 Correct 68 ms 25160 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 22800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22876 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 21084 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 7 ms 23132 KB Output is correct
12 Correct 6 ms 23128 KB Output is correct
13 Correct 6 ms 21104 KB Output is correct
14 Correct 9 ms 23132 KB Output is correct
15 Correct 6 ms 20828 KB Output is correct
16 Correct 8 ms 23132 KB Output is correct
17 Correct 5 ms 23092 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23128 KB Output is correct
21 Correct 495 ms 22552 KB Output is correct
22 Correct 369 ms 25936 KB Output is correct
23 Correct 509 ms 22476 KB Output is correct
24 Correct 485 ms 24276 KB Output is correct
25 Correct 414 ms 25928 KB Output is correct
26 Correct 396 ms 26056 KB Output is correct
27 Correct 36 ms 23244 KB Output is correct
28 Correct 38 ms 22736 KB Output is correct
29 Correct 786 ms 24492 KB Output is correct
30 Correct 774 ms 24752 KB Output is correct
31 Correct 829 ms 23856 KB Output is correct
32 Correct 794 ms 24084 KB Output is correct
33 Correct 160 ms 25928 KB Output is correct
34 Correct 237 ms 24904 KB Output is correct
35 Correct 63 ms 26336 KB Output is correct
36 Correct 68 ms 25160 KB Output is correct
37 Correct 645 ms 25108 KB Output is correct
38 Correct 772 ms 23928 KB Output is correct
39 Correct 29 ms 22612 KB Output is correct
40 Correct 35 ms 24840 KB Output is correct
41 Execution timed out 1071 ms 22276 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 24300 KB Output is correct
2 Correct 448 ms 26368 KB Output is correct
3 Correct 559 ms 26576 KB Output is correct
4 Correct 490 ms 23440 KB Output is correct
5 Correct 632 ms 24020 KB Output is correct
6 Correct 744 ms 24832 KB Output is correct
7 Correct 51 ms 23484 KB Output is correct
8 Correct 50 ms 23528 KB Output is correct
9 Execution timed out 1016 ms 21232 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22876 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 21084 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 7 ms 23132 KB Output is correct
12 Correct 6 ms 23128 KB Output is correct
13 Correct 6 ms 21104 KB Output is correct
14 Correct 9 ms 23132 KB Output is correct
15 Correct 6 ms 20828 KB Output is correct
16 Correct 8 ms 23132 KB Output is correct
17 Correct 5 ms 23092 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23128 KB Output is correct
21 Correct 6 ms 23132 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct
23 Correct 6 ms 21088 KB Output is correct
24 Correct 6 ms 21084 KB Output is correct
25 Correct 5 ms 23020 KB Output is correct
26 Correct 4 ms 23020 KB Output is correct
27 Correct 6 ms 23132 KB Output is correct
28 Correct 6 ms 23132 KB Output is correct
29 Correct 6 ms 23108 KB Output is correct
30 Correct 7 ms 21096 KB Output is correct
31 Correct 8 ms 23132 KB Output is correct
32 Correct 6 ms 21084 KB Output is correct
33 Correct 6 ms 21084 KB Output is correct
34 Correct 8 ms 23132 KB Output is correct
35 Correct 7 ms 23132 KB Output is correct
36 Correct 7 ms 21084 KB Output is correct
37 Correct 4 ms 23132 KB Output is correct
38 Correct 5 ms 23140 KB Output is correct
39 Correct 495 ms 22552 KB Output is correct
40 Correct 369 ms 25936 KB Output is correct
41 Correct 509 ms 22476 KB Output is correct
42 Correct 485 ms 24276 KB Output is correct
43 Correct 414 ms 25928 KB Output is correct
44 Correct 396 ms 26056 KB Output is correct
45 Correct 36 ms 23244 KB Output is correct
46 Correct 38 ms 22736 KB Output is correct
47 Correct 786 ms 24492 KB Output is correct
48 Correct 774 ms 24752 KB Output is correct
49 Correct 829 ms 23856 KB Output is correct
50 Correct 794 ms 24084 KB Output is correct
51 Correct 160 ms 25928 KB Output is correct
52 Correct 237 ms 24904 KB Output is correct
53 Correct 63 ms 26336 KB Output is correct
54 Correct 68 ms 25160 KB Output is correct
55 Correct 645 ms 25108 KB Output is correct
56 Correct 772 ms 23928 KB Output is correct
57 Correct 29 ms 22612 KB Output is correct
58 Correct 35 ms 24840 KB Output is correct
59 Execution timed out 1071 ms 22276 KB Time limit exceeded
60 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22876 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 21084 KB Output is correct
5 Correct 4 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 7 ms 23132 KB Output is correct
8 Correct 7 ms 23132 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 7 ms 23132 KB Output is correct
11 Correct 7 ms 23132 KB Output is correct
12 Correct 6 ms 23128 KB Output is correct
13 Correct 6 ms 21104 KB Output is correct
14 Correct 9 ms 23132 KB Output is correct
15 Correct 6 ms 20828 KB Output is correct
16 Correct 8 ms 23132 KB Output is correct
17 Correct 5 ms 23092 KB Output is correct
18 Correct 8 ms 21084 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 5 ms 23128 KB Output is correct
21 Correct 6 ms 23132 KB Output is correct
22 Correct 5 ms 21084 KB Output is correct
23 Correct 6 ms 21088 KB Output is correct
24 Correct 6 ms 21084 KB Output is correct
25 Correct 5 ms 23020 KB Output is correct
26 Correct 4 ms 23020 KB Output is correct
27 Correct 6 ms 23132 KB Output is correct
28 Correct 6 ms 23132 KB Output is correct
29 Correct 6 ms 23108 KB Output is correct
30 Correct 7 ms 21096 KB Output is correct
31 Correct 8 ms 23132 KB Output is correct
32 Correct 6 ms 21084 KB Output is correct
33 Correct 6 ms 21084 KB Output is correct
34 Correct 8 ms 23132 KB Output is correct
35 Correct 7 ms 23132 KB Output is correct
36 Correct 7 ms 21084 KB Output is correct
37 Correct 4 ms 23132 KB Output is correct
38 Correct 5 ms 23140 KB Output is correct
39 Correct 495 ms 22552 KB Output is correct
40 Correct 369 ms 25936 KB Output is correct
41 Correct 509 ms 22476 KB Output is correct
42 Correct 485 ms 24276 KB Output is correct
43 Correct 414 ms 25928 KB Output is correct
44 Correct 396 ms 26056 KB Output is correct
45 Correct 36 ms 23244 KB Output is correct
46 Correct 38 ms 22736 KB Output is correct
47 Correct 786 ms 24492 KB Output is correct
48 Correct 774 ms 24752 KB Output is correct
49 Correct 829 ms 23856 KB Output is correct
50 Correct 794 ms 24084 KB Output is correct
51 Correct 160 ms 25928 KB Output is correct
52 Correct 237 ms 24904 KB Output is correct
53 Correct 63 ms 26336 KB Output is correct
54 Correct 68 ms 25160 KB Output is correct
55 Execution timed out 1049 ms 22800 KB Time limit exceeded
56 Halted 0 ms 0 KB -