oj.uz

Submission #783267

# Submission time Handle Problem Language Result Execution time Memory
783267 2023-07-14T19:21:38 Z Dan4Life Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = 65010;
int n, m, q, tot[mxN], del[mxN];
vector<array<int,2>> shop[mxN];

void add(int i, int x, int v){
	if(sz(shop[i]) and shop[i].back()[0]==x) shop[i].back()[1]+=v,tot[i]+=v;
	else shop[i].pb({x,v+(sz(shop[i])?shop[i].back()[1]:0)}),tot[i]+=v;
} 

void rem(int i, int v){
	if(tot[i]<=v) del[i]+=tot[i], tot[i]=0;
	else del[i]+=v, tot[i]-=v;
}

int get(int i, int v){
	v+=del[i]; if(!sz(shop[i]) or shop[i].back()[1]<v) return 0;
	int l = 0, r = sz(shop[i])-1;
	while(l<r){
		int mid = (l+r)/2;
		if(shop[i][mid][1]<v) l=mid+1;
		else r=mid;
	}
	return shop[i][l][0];
}

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> q;
	while(q--){
		int t, l, r, x, v; cin >> t;
		if(t==1){
			cin >> l >> r >> x >> v;
			for(int i = l; i <= r; i++) add(i,x,v);
		}
		else if(t==2){
			cin >> l >> r >> v;
			for(int i = l; i <= r; i++) rem(i,v);
		}
		else cin >> x >> v, cout << get(x,v) << "\n";
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7636 KB Output is correct
2 Correct 12 ms 13372 KB Output is correct
3 Correct 15 ms 15132 KB Output is correct
4 Correct 25 ms 25784 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 26 ms 19236 KB Output is correct
8 Correct 21 ms 18768 KB Output is correct
9 Correct 19 ms 18848 KB Output is correct
10 Correct 19 ms 19796 KB Output is correct
11 Correct 20 ms 20308 KB Output is correct
12 Correct 19 ms 19332 KB Output is correct
13 Correct 26 ms 27672 KB Output is correct
14 Correct 35 ms 32716 KB Output is correct
15 Correct 22 ms 17492 KB Output is correct
16 Correct 34 ms 32484 KB Output is correct
17 Correct 12 ms 10856 KB Output is correct
18 Correct 20 ms 15572 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7636 KB Output is correct
2 Correct 12 ms 13372 KB Output is correct
3 Correct 15 ms 15132 KB Output is correct
4 Correct 25 ms 25784 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 26 ms 19236 KB Output is correct
8 Correct 21 ms 18768 KB Output is correct
9 Correct 19 ms 18848 KB Output is correct
10 Correct 19 ms 19796 KB Output is correct
11 Correct 20 ms 20308 KB Output is correct
12 Correct 19 ms 19332 KB Output is correct
13 Correct 26 ms 27672 KB Output is correct
14 Correct 35 ms 32716 KB Output is correct
15 Correct 22 ms 17492 KB Output is correct
16 Correct 34 ms 32484 KB Output is correct
17 Correct 12 ms 10856 KB Output is correct
18 Correct 20 ms 15572 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 11 ms 12196 KB Output is correct
22 Correct 12 ms 13404 KB Output is correct
23 Correct 16 ms 17396 KB Output is correct
24 Correct 25 ms 25860 KB Output is correct
25 Correct 2 ms 1876 KB Output is correct
26 Correct 1 ms 1876 KB Output is correct
27 Correct 17 ms 16672 KB Output is correct
28 Correct 20 ms 19616 KB Output is correct
29 Correct 19 ms 19556 KB Output is correct
30 Correct 26 ms 19152 KB Output is correct
31 Correct 19 ms 16140 KB Output is correct
32 Correct 20 ms 15964 KB Output is correct
33 Correct 28 ms 26040 KB Output is correct
34 Correct 34 ms 32588 KB Output is correct
35 Correct 24 ms 24532 KB Output is correct
36 Correct 35 ms 32168 KB Output is correct
37 Correct 2 ms 2004 KB Output is correct
38 Correct 3 ms 2132 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 6192 KB Output is correct
2 Correct 708 ms 9152 KB Output is correct
3 Correct 933 ms 10080 KB Output is correct
4 Correct 935 ms 10024 KB Output is correct
5 Correct 721 ms 13428 KB Output is correct
6 Correct 733 ms 13048 KB Output is correct
7 Correct 14 ms 3288 KB Output is correct
8 Correct 14 ms 3516 KB Output is correct
9 Execution timed out 1077 ms 7008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 3540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7636 KB Output is correct
2 Correct 12 ms 13372 KB Output is correct
3 Correct 15 ms 15132 KB Output is correct
4 Correct 25 ms 25784 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 26 ms 19236 KB Output is correct
8 Correct 21 ms 18768 KB Output is correct
9 Correct 19 ms 18848 KB Output is correct
10 Correct 19 ms 19796 KB Output is correct
11 Correct 20 ms 20308 KB Output is correct
12 Correct 19 ms 19332 KB Output is correct
13 Correct 26 ms 27672 KB Output is correct
14 Correct 35 ms 32716 KB Output is correct
15 Correct 22 ms 17492 KB Output is correct
16 Correct 34 ms 32484 KB Output is correct
17 Correct 12 ms 10856 KB Output is correct
18 Correct 20 ms 15572 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 908 ms 6192 KB Output is correct
22 Correct 708 ms 9152 KB Output is correct
23 Correct 933 ms 10080 KB Output is correct
24 Correct 935 ms 10024 KB Output is correct
25 Correct 721 ms 13428 KB Output is correct
26 Correct 733 ms 13048 KB Output is correct
27 Correct 14 ms 3288 KB Output is correct
28 Correct 14 ms 3516 KB Output is correct
29 Execution timed out 1077 ms 7008 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 849 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7636 KB Output is correct
2 Correct 12 ms 13372 KB Output is correct
3 Correct 15 ms 15132 KB Output is correct
4 Correct 25 ms 25784 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 26 ms 19236 KB Output is correct
8 Correct 21 ms 18768 KB Output is correct
9 Correct 19 ms 18848 KB Output is correct
10 Correct 19 ms 19796 KB Output is correct
11 Correct 20 ms 20308 KB Output is correct
12 Correct 19 ms 19332 KB Output is correct
13 Correct 26 ms 27672 KB Output is correct
14 Correct 35 ms 32716 KB Output is correct
15 Correct 22 ms 17492 KB Output is correct
16 Correct 34 ms 32484 KB Output is correct
17 Correct 12 ms 10856 KB Output is correct
18 Correct 20 ms 15572 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 11 ms 12196 KB Output is correct
22 Correct 12 ms 13404 KB Output is correct
23 Correct 16 ms 17396 KB Output is correct
24 Correct 25 ms 25860 KB Output is correct
25 Correct 2 ms 1876 KB Output is correct
26 Correct 1 ms 1876 KB Output is correct
27 Correct 17 ms 16672 KB Output is correct
28 Correct 20 ms 19616 KB Output is correct
29 Correct 19 ms 19556 KB Output is correct
30 Correct 26 ms 19152 KB Output is correct
31 Correct 19 ms 16140 KB Output is correct
32 Correct 20 ms 15964 KB Output is correct
33 Correct 28 ms 26040 KB Output is correct
34 Correct 34 ms 32588 KB Output is correct
35 Correct 24 ms 24532 KB Output is correct
36 Correct 35 ms 32168 KB Output is correct
37 Correct 2 ms 2004 KB Output is correct
38 Correct 3 ms 2132 KB Output is correct
39 Correct 908 ms 6192 KB Output is correct
40 Correct 708 ms 9152 KB Output is correct
41 Correct 933 ms 10080 KB Output is correct
42 Correct 935 ms 10024 KB Output is correct
43 Correct 721 ms 13428 KB Output is correct
44 Correct 733 ms 13048 KB Output is correct
45 Correct 14 ms 3288 KB Output is correct
46 Correct 14 ms 3516 KB Output is correct
47 Execution timed out 1077 ms 7008 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7636 KB Output is correct
2 Correct 12 ms 13372 KB Output is correct
3 Correct 15 ms 15132 KB Output is correct
4 Correct 25 ms 25784 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 26 ms 19236 KB Output is correct
8 Correct 21 ms 18768 KB Output is correct
9 Correct 19 ms 18848 KB Output is correct
10 Correct 19 ms 19796 KB Output is correct
11 Correct 20 ms 20308 KB Output is correct
12 Correct 19 ms 19332 KB Output is correct
13 Correct 26 ms 27672 KB Output is correct
14 Correct 35 ms 32716 KB Output is correct
15 Correct 22 ms 17492 KB Output is correct
16 Correct 34 ms 32484 KB Output is correct
17 Correct 12 ms 10856 KB Output is correct
18 Correct 20 ms 15572 KB Output is correct
19 Correct 2 ms 2132 KB Output is correct
20 Correct 2 ms 2132 KB Output is correct
21 Correct 11 ms 12196 KB Output is correct
22 Correct 12 ms 13404 KB Output is correct
23 Correct 16 ms 17396 KB Output is correct
24 Correct 25 ms 25860 KB Output is correct
25 Correct 2 ms 1876 KB Output is correct
26 Correct 1 ms 1876 KB Output is correct
27 Correct 17 ms 16672 KB Output is correct
28 Correct 20 ms 19616 KB Output is correct
29 Correct 19 ms 19556 KB Output is correct
30 Correct 26 ms 19152 KB Output is correct
31 Correct 19 ms 16140 KB Output is correct
32 Correct 20 ms 15964 KB Output is correct
33 Correct 28 ms 26040 KB Output is correct
34 Correct 34 ms 32588 KB Output is correct
35 Correct 24 ms 24532 KB Output is correct
36 Correct 35 ms 32168 KB Output is correct
37 Correct 2 ms 2004 KB Output is correct
38 Correct 3 ms 2132 KB Output is correct
39 Correct 908 ms 6192 KB Output is correct
40 Correct 708 ms 9152 KB Output is correct
41 Correct 933 ms 10080 KB Output is correct
42 Correct 935 ms 10024 KB Output is correct
43 Correct 721 ms 13428 KB Output is correct
44 Correct 733 ms 13048 KB Output is correct
45 Correct 14 ms 3288 KB Output is correct
46 Correct 14 ms 3516 KB Output is correct
47 Execution timed out 1077 ms 7008 KB Time limit exceeded
48 Halted 0 ms 0 KB -