oj.uz

답안 #416259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416259 2021-06-02T08:54:47 Z amoo_safar 푸드 코트 (JOI21_foodcourt) C++17
68 / 100
 1000 ms 41284 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 25e4 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

typedef pll pii;

pii seg[N << 2]; // sum ans
pii nl = {0, 0};
pii Merge(pii A, pii B){
	return {A.F + B.F, min(A.S, A.F + B.S)};
}
void Apply(int id, pii X){
	seg[id] = Merge(seg[id], X);
}
void Shift(int id){
	Apply(id << 1, seg[id]);
	Apply(id << 1 | 1, seg[id]);
	seg[id] = nl;
}
void Add(int id, int l, int r, pii X, int L, int R){
	if(r <= L || R <= l) return ;
	if(l <= L && R <= r){
		Apply(id, X);
		return ;
	}
	int mid = (L + R) >> 1;
	Shift(id);
	Add(id << 1, l, r, X, L, mid);
	Add(id<<1|1, l, r, X, mid, R);
}
pll Get(int id, int idx, int L, int R){
	if(L + 1 == R) return seg[id];
	int mid = (L + R) >> 1;
	Shift(id);
	if(idx < mid)
		return Get(id << 1, idx, L, mid);
	return Get(id << 1 | 1, idx, mid, R);
}

ll fen[N];
void Add(int idx, ll x){
	for(; idx < N; idx += idx & (-idx))
		fen[idx] += x;
}
ll Get(int idx){
	ll res = 0;
	for(; idx; idx -= idx & (-idx))
		res += fen[idx];
	return res;
}


int t[N];
ll a[N], b[N], c[N], d[N], ps[N];
int lf[N], rt[N];
vector<int> V[N];


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1)
			cin >> a[i] >> b[i] >> c[i] >> d[i];
		if(t[i] == 2){
			cin >> a[i] >> b[i] >> c[i];
			Add(a[i], c[i]);
			Add(b[i] + 1, -c[i]);
		}
		if(t[i] == 3){
			cin >> a[i] >> b[i];
			lf[i] = 0;
			rt[i] = i + 1;
			ps[i] = Get(a[i]);
		}
	}
	for(int _ = 0; _ < 20; _++){
		// debug(_);
		for(int i = 1; i <= q; i++) V[i].clear();
		memset(fen, 0, sizeof fen);
		fill(seg, seg + (N << 2), nl);

		int mid;
		for(int i = 1; i <= q; i++){
			if(t[i] == 3 && lf[i] + 1 < rt[i]){
				// if(_>18) debug(_);
				mid = (lf[i] + rt[i]) >> 1;
				// debug(mid);
				V[mid].pb(i);
			}
		}

		for(int i = 1; i <= q; i++){
			// debug(i);
			if(t[i] == 1){
				Add(1, a[i], b[i] + 1, {d[i], 0}, 1, n + 1);
			} else if(t[i] == 2){
				Add(1, a[i], b[i] + 1, {-c[i], -c[i]}, 1, n + 1);
				
				Add(a[i], c[i]);
				Add(b[i] + 1, -c[i]);
			}
			for(int q_id : V[i]){
				pll res = Get(1, a[q_id], 1, n + 1);
				ll nw = res.F - res.S;
				ll dec = (ps[q_id] - Get(a[q_id]));
				assert(dec >= 0);
				nw -= dec; 
				if(nw >= b[q_id])
					rt[q_id] = i;
				else
					lf[q_id] = i;
			}
		}
	}
	for(int i = 1; i <= q; i++){
		if(t[i] != 3) continue;
		if(rt[i] == i + 1) cout << "0\n";
		else
			cout << c[rt[i]] << '\n';
	}
	return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23956 KB Output is correct
2 Correct 84 ms 24004 KB Output is correct
3 Correct 74 ms 23940 KB Output is correct
4 Correct 84 ms 24092 KB Output is correct
5 Correct 67 ms 23884 KB Output is correct
6 Correct 79 ms 23988 KB Output is correct
7 Correct 92 ms 23976 KB Output is correct
8 Correct 91 ms 24004 KB Output is correct
9 Correct 89 ms 23976 KB Output is correct
10 Correct 90 ms 23992 KB Output is correct
11 Correct 90 ms 23996 KB Output is correct
12 Correct 91 ms 23972 KB Output is correct
13 Correct 77 ms 23956 KB Output is correct
14 Correct 79 ms 23996 KB Output is correct
15 Correct 89 ms 23960 KB Output is correct
16 Correct 83 ms 24000 KB Output is correct
17 Correct 83 ms 23964 KB Output is correct
18 Correct 77 ms 23940 KB Output is correct
19 Correct 71 ms 23972 KB Output is correct
20 Correct 72 ms 23968 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23956 KB Output is correct
2 Correct 84 ms 24004 KB Output is correct
3 Correct 74 ms 23940 KB Output is correct
4 Correct 84 ms 24092 KB Output is correct
5 Correct 67 ms 23884 KB Output is correct
6 Correct 79 ms 23988 KB Output is correct
7 Correct 92 ms 23976 KB Output is correct
8 Correct 91 ms 24004 KB Output is correct
9 Correct 89 ms 23976 KB Output is correct
10 Correct 90 ms 23992 KB Output is correct
11 Correct 90 ms 23996 KB Output is correct
12 Correct 91 ms 23972 KB Output is correct
13 Correct 77 ms 23956 KB Output is correct
14 Correct 79 ms 23996 KB Output is correct
15 Correct 89 ms 23960 KB Output is correct
16 Correct 83 ms 24000 KB Output is correct
17 Correct 83 ms 23964 KB Output is correct
18 Correct 77 ms 23940 KB Output is correct
19 Correct 71 ms 23972 KB Output is correct
20 Correct 72 ms 23968 KB Output is correct
21 Correct 77 ms 23988 KB Output is correct
22 Correct 79 ms 23980 KB Output is correct
23 Correct 80 ms 23984 KB Output is correct
24 Correct 78 ms 23996 KB Output is correct
25 Correct 65 ms 23964 KB Output is correct
26 Correct 71 ms 23964 KB Output is correct
27 Correct 83 ms 23964 KB Output is correct
28 Correct 77 ms 23992 KB Output is correct
29 Correct 78 ms 23972 KB Output is correct
30 Correct 80 ms 23984 KB Output is correct
31 Correct 74 ms 23992 KB Output is correct
32 Correct 76 ms 24004 KB Output is correct
33 Correct 64 ms 23996 KB Output is correct
34 Correct 66 ms 24000 KB Output is correct
35 Correct 72 ms 23988 KB Output is correct
36 Correct 74 ms 23996 KB Output is correct
37 Correct 68 ms 23936 KB Output is correct
38 Correct 74 ms 23972 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 687 ms 29156 KB Output is correct
2 Correct 688 ms 29092 KB Output is correct
3 Correct 696 ms 29124 KB Output is correct
4 Correct 710 ms 29124 KB Output is correct
5 Correct 729 ms 29132 KB Output is correct
6 Correct 704 ms 29124 KB Output is correct
7 Correct 165 ms 28868 KB Output is correct
8 Correct 172 ms 28824 KB Output is correct
9 Correct 765 ms 28916 KB Output is correct
10 Correct 735 ms 29132 KB Output is correct
11 Correct 735 ms 29128 KB Output is correct
12 Correct 731 ms 29192 KB Output is correct
13 Correct 535 ms 28612 KB Output is correct
14 Correct 654 ms 29212 KB Output is correct
15 Correct 606 ms 29056 KB Output is correct
16 Correct 603 ms 28976 KB Output is correct

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 41284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23956 KB Output is correct
2 Correct 84 ms 24004 KB Output is correct
3 Correct 74 ms 23940 KB Output is correct
4 Correct 84 ms 24092 KB Output is correct
5 Correct 67 ms 23884 KB Output is correct
6 Correct 79 ms 23988 KB Output is correct
7 Correct 92 ms 23976 KB Output is correct
8 Correct 91 ms 24004 KB Output is correct
9 Correct 89 ms 23976 KB Output is correct
10 Correct 90 ms 23992 KB Output is correct
11 Correct 90 ms 23996 KB Output is correct
12 Correct 91 ms 23972 KB Output is correct
13 Correct 77 ms 23956 KB Output is correct
14 Correct 79 ms 23996 KB Output is correct
15 Correct 89 ms 23960 KB Output is correct
16 Correct 83 ms 24000 KB Output is correct
17 Correct 83 ms 23964 KB Output is correct
18 Correct 77 ms 23940 KB Output is correct
19 Correct 71 ms 23972 KB Output is correct
20 Correct 72 ms 23968 KB Output is correct
21 Correct 687 ms 29156 KB Output is correct
22 Correct 688 ms 29092 KB Output is correct
23 Correct 696 ms 29124 KB Output is correct
24 Correct 710 ms 29124 KB Output is correct
25 Correct 729 ms 29132 KB Output is correct
26 Correct 704 ms 29124 KB Output is correct
27 Correct 165 ms 28868 KB Output is correct
28 Correct 172 ms 28824 KB Output is correct
29 Correct 765 ms 28916 KB Output is correct
30 Correct 735 ms 29132 KB Output is correct
31 Correct 735 ms 29128 KB Output is correct
32 Correct 731 ms 29192 KB Output is correct
33 Correct 535 ms 28612 KB Output is correct
34 Correct 654 ms 29212 KB Output is correct
35 Correct 606 ms 29056 KB Output is correct
36 Correct 603 ms 28976 KB Output is correct
37 Correct 754 ms 28700 KB Output is correct
38 Correct 723 ms 27972 KB Output is correct
39 Correct 164 ms 28100 KB Output is correct
40 Correct 189 ms 28800 KB Output is correct
41 Correct 890 ms 28804 KB Output is correct
42 Correct 910 ms 29088 KB Output is correct
43 Correct 900 ms 29288 KB Output is correct
44 Correct 896 ms 28900 KB Output is correct
45 Correct 912 ms 29148 KB Output is correct
46 Correct 906 ms 29132 KB Output is correct
47 Correct 269 ms 29336 KB Output is correct
48 Correct 717 ms 29184 KB Output is correct
49 Correct 632 ms 27548 KB Output is correct
50 Correct 791 ms 28340 KB Output is correct
51 Correct 925 ms 29100 KB Output is correct
52 Correct 889 ms 29172 KB Output is correct
53 Correct 493 ms 27976 KB Output is correct
54 Correct 581 ms 28984 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 28668 KB Output is correct
2 Correct 710 ms 29264 KB Output is correct
3 Correct 747 ms 29260 KB Output is correct
4 Correct 544 ms 27724 KB Output is correct
5 Correct 631 ms 28484 KB Output is correct
6 Correct 745 ms 29280 KB Output is correct
7 Correct 162 ms 28744 KB Output is correct
8 Correct 155 ms 28404 KB Output is correct
9 Correct 315 ms 29284 KB Output is correct
10 Correct 484 ms 27624 KB Output is correct
11 Correct 664 ms 29316 KB Output is correct
12 Correct 681 ms 29224 KB Output is correct

Subtask #7
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23956 KB Output is correct
2 Correct 84 ms 24004 KB Output is correct
3 Correct 74 ms 23940 KB Output is correct
4 Correct 84 ms 24092 KB Output is correct
5 Correct 67 ms 23884 KB Output is correct
6 Correct 79 ms 23988 KB Output is correct
7 Correct 92 ms 23976 KB Output is correct
8 Correct 91 ms 24004 KB Output is correct
9 Correct 89 ms 23976 KB Output is correct
10 Correct 90 ms 23992 KB Output is correct
11 Correct 90 ms 23996 KB Output is correct
12 Correct 91 ms 23972 KB Output is correct
13 Correct 77 ms 23956 KB Output is correct
14 Correct 79 ms 23996 KB Output is correct
15 Correct 89 ms 23960 KB Output is correct
16 Correct 83 ms 24000 KB Output is correct
17 Correct 83 ms 23964 KB Output is correct
18 Correct 77 ms 23940 KB Output is correct
19 Correct 71 ms 23972 KB Output is correct
20 Correct 72 ms 23968 KB Output is correct
21 Correct 77 ms 23988 KB Output is correct
22 Correct 79 ms 23980 KB Output is correct
23 Correct 80 ms 23984 KB Output is correct
24 Correct 78 ms 23996 KB Output is correct
25 Correct 65 ms 23964 KB Output is correct
26 Correct 71 ms 23964 KB Output is correct
27 Correct 83 ms 23964 KB Output is correct
28 Correct 77 ms 23992 KB Output is correct
29 Correct 78 ms 23972 KB Output is correct
30 Correct 80 ms 23984 KB Output is correct
31 Correct 74 ms 23992 KB Output is correct
32 Correct 76 ms 24004 KB Output is correct
33 Correct 64 ms 23996 KB Output is correct
34 Correct 66 ms 24000 KB Output is correct
35 Correct 72 ms 23988 KB Output is correct
36 Correct 74 ms 23996 KB Output is correct
37 Correct 68 ms 23936 KB Output is correct
38 Correct 74 ms 23972 KB Output is correct
39 Correct 687 ms 29156 KB Output is correct
40 Correct 688 ms 29092 KB Output is correct
41 Correct 696 ms 29124 KB Output is correct
42 Correct 710 ms 29124 KB Output is correct
43 Correct 729 ms 29132 KB Output is correct
44 Correct 704 ms 29124 KB Output is correct
45 Correct 165 ms 28868 KB Output is correct
46 Correct 172 ms 28824 KB Output is correct
47 Correct 765 ms 28916 KB Output is correct
48 Correct 735 ms 29132 KB Output is correct
49 Correct 735 ms 29128 KB Output is correct
50 Correct 731 ms 29192 KB Output is correct
51 Correct 535 ms 28612 KB Output is correct
52 Correct 654 ms 29212 KB Output is correct
53 Correct 606 ms 29056 KB Output is correct
54 Correct 603 ms 28976 KB Output is correct
55 Correct 754 ms 28700 KB Output is correct
56 Correct 723 ms 27972 KB Output is correct
57 Correct 164 ms 28100 KB Output is correct
58 Correct 189 ms 28800 KB Output is correct
59 Correct 890 ms 28804 KB Output is correct
60 Correct 910 ms 29088 KB Output is correct
61 Correct 900 ms 29288 KB Output is correct
62 Correct 896 ms 28900 KB Output is correct
63 Correct 912 ms 29148 KB Output is correct
64 Correct 906 ms 29132 KB Output is correct
65 Correct 269 ms 29336 KB Output is correct
66 Correct 717 ms 29184 KB Output is correct
67 Correct 632 ms 27548 KB Output is correct
68 Correct 791 ms 28340 KB Output is correct
69 Correct 925 ms 29100 KB Output is correct
70 Correct 889 ms 29172 KB Output is correct
71 Correct 493 ms 27976 KB Output is correct
72 Correct 581 ms 28984 KB Output is correct
73 Correct 682 ms 28668 KB Output is correct
74 Correct 710 ms 29264 KB Output is correct
75 Correct 747 ms 29260 KB Output is correct
76 Correct 544 ms 27724 KB Output is correct
77 Correct 631 ms 28484 KB Output is correct
78 Correct 745 ms 29280 KB Output is correct
79 Correct 162 ms 28744 KB Output is correct
80 Correct 155 ms 28404 KB Output is correct
81 Correct 315 ms 29284 KB Output is correct
82 Correct 484 ms 27624 KB Output is correct
83 Correct 664 ms 29316 KB Output is correct
84 Correct 681 ms 29224 KB Output is correct
85 Correct 748 ms 28688 KB Output is correct
86 Correct 839 ms 29228 KB Output is correct
87 Correct 777 ms 28368 KB Output is correct
88 Correct 892 ms 29088 KB Output is correct
89 Correct 614 ms 27204 KB Output is correct
90 Correct 893 ms 29184 KB Output is correct
91 Correct 722 ms 28264 KB Output is correct
92 Correct 670 ms 28012 KB Output is correct
93 Correct 892 ms 29136 KB Output is correct
94 Correct 915 ms 28996 KB Output is correct
95 Correct 879 ms 28984 KB Output is correct
96 Correct 891 ms 29128 KB Output is correct
97 Correct 889 ms 29076 KB Output is correct
98 Correct 725 ms 28472 KB Output is correct
99 Correct 272 ms 29232 KB Output is correct
100 Correct 632 ms 28372 KB Output is correct
101 Correct 723 ms 29252 KB Output is correct
102 Correct 661 ms 28500 KB Output is correct

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 23956 KB Output is correct
2 Correct 84 ms 24004 KB Output is correct
3 Correct 74 ms 23940 KB Output is correct
4 Correct 84 ms 24092 KB Output is correct
5 Correct 67 ms 23884 KB Output is correct
6 Correct 79 ms 23988 KB Output is correct
7 Correct 92 ms 23976 KB Output is correct
8 Correct 91 ms 24004 KB Output is correct
9 Correct 89 ms 23976 KB Output is correct
10 Correct 90 ms 23992 KB Output is correct
11 Correct 90 ms 23996 KB Output is correct
12 Correct 91 ms 23972 KB Output is correct
13 Correct 77 ms 23956 KB Output is correct
14 Correct 79 ms 23996 KB Output is correct
15 Correct 89 ms 23960 KB Output is correct
16 Correct 83 ms 24000 KB Output is correct
17 Correct 83 ms 23964 KB Output is correct
18 Correct 77 ms 23940 KB Output is correct
19 Correct 71 ms 23972 KB Output is correct
20 Correct 72 ms 23968 KB Output is correct
21 Correct 77 ms 23988 KB Output is correct
22 Correct 79 ms 23980 KB Output is correct
23 Correct 80 ms 23984 KB Output is correct
24 Correct 78 ms 23996 KB Output is correct
25 Correct 65 ms 23964 KB Output is correct
26 Correct 71 ms 23964 KB Output is correct
27 Correct 83 ms 23964 KB Output is correct
28 Correct 77 ms 23992 KB Output is correct
29 Correct 78 ms 23972 KB Output is correct
30 Correct 80 ms 23984 KB Output is correct
31 Correct 74 ms 23992 KB Output is correct
32 Correct 76 ms 24004 KB Output is correct
33 Correct 64 ms 23996 KB Output is correct
34 Correct 66 ms 24000 KB Output is correct
35 Correct 72 ms 23988 KB Output is correct
36 Correct 74 ms 23996 KB Output is correct
37 Correct 68 ms 23936 KB Output is correct
38 Correct 74 ms 23972 KB Output is correct
39 Correct 687 ms 29156 KB Output is correct
40 Correct 688 ms 29092 KB Output is correct
41 Correct 696 ms 29124 KB Output is correct
42 Correct 710 ms 29124 KB Output is correct
43 Correct 729 ms 29132 KB Output is correct
44 Correct 704 ms 29124 KB Output is correct
45 Correct 165 ms 28868 KB Output is correct
46 Correct 172 ms 28824 KB Output is correct
47 Correct 765 ms 28916 KB Output is correct
48 Correct 735 ms 29132 KB Output is correct
49 Correct 735 ms 29128 KB Output is correct
50 Correct 731 ms 29192 KB Output is correct
51 Correct 535 ms 28612 KB Output is correct
52 Correct 654 ms 29212 KB Output is correct
53 Correct 606 ms 29056 KB Output is correct
54 Correct 603 ms 28976 KB Output is correct
55 Execution timed out 1087 ms 41284 KB Time limit exceeded
56 Halted 0 ms 0 KB -