oj.uz

Submission #1042218

# Submission time Handle Problem Language Result Execution time Memory
1042218 2024-08-02T16:15:52 Z flappybird Sushi (JOI16_sushi) C++17
20 / 100
 12000 ms 123476 KB 
//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#else
#define DEBUG(...) 1234
#endif
#define B 2000
int A[MAX];
multiset<int> all[MAX];
priority_queue<int, vector<int>, greater<int>> upd[MAX];
int N, Q;
void prop(int id) {
	all[id].clear();
	int i;
	for (i = id * B; i < min(N, (id + 1) * B); i++) {
		upd[id].emplace(A[i]);
		A[i] = upd[id].top();
		upd[id].pop();
		all[id].emplace(A[i]);
	}
	upd[id] = {};
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> Q;
	int i;
	for (i = 0; i < N; i++) cin >> A[i];
	for (i = 0; i < N; i++) all[i / B].insert(A[i]);
	auto f = [&](int l, int r, int x) {
		int i;
		i = l;
		while (i <= r) {
			int b = i / B;
			if ((i % B == 0) && i + B - 1 <= r) {
				//DEBUG("ii" << i << ln);
				upd[b].push(x);
				all[b].insert(x);
				x = *all[b].rbegin();
				all[b].erase(all[b].find(x));
				i += B;
				//DEBUG('x' << x << bb);
			}
			else {
				if (upd[b].size()) prop(b);
				//DEBUG('i' << i << bb << A[i] << bb << x << ln);
				if (A[i] > x) {
					all[b].insert(x);
					all[b].erase(all[b].find(A[i]));
					swap(A[i], x);
				}
				i++;
				//DEBUG('y' << x << bb);
			}
		}
		return x;
	};
	while (Q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l--;
		r--;
		if (l > r) {
			x = f(l, N - 1, x);
			x = f(0, r, x);
		}
		else x = f(l, r, x);
		cout << x << ln;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 80732 KB Output is correct
2 Correct 27 ms 80732 KB Output is correct
3 Correct 28 ms 80580 KB Output is correct
4 Correct 28 ms 80732 KB Output is correct
5 Correct 27 ms 80728 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 23 ms 80548 KB Output is correct
8 Correct 24 ms 80688 KB Output is correct
9 Correct 29 ms 80732 KB Output is correct
10 Correct 30 ms 80732 KB Output is correct
11 Correct 88 ms 80728 KB Output is correct
12 Correct 86 ms 80508 KB Output is correct
13 Correct 59 ms 80608 KB Output is correct
14 Correct 32 ms 80728 KB Output is correct
15 Correct 37 ms 80764 KB Output is correct
16 Correct 19 ms 80732 KB Output is correct
17 Correct 19 ms 80628 KB Output is correct
18 Correct 20 ms 80476 KB Output is correct
19 Correct 19 ms 80476 KB Output is correct
20 Correct 19 ms 80476 KB Output is correct
21 Correct 22 ms 80476 KB Output is correct
22 Correct 21 ms 80476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2665 ms 123088 KB Output is correct
2 Correct 2676 ms 123212 KB Output is correct
3 Correct 3381 ms 123220 KB Output is correct
4 Correct 2688 ms 123220 KB Output is correct
5 Correct 2567 ms 123428 KB Output is correct
6 Correct 4986 ms 123216 KB Output is correct
7 Correct 5083 ms 123428 KB Output is correct
8 Correct 5215 ms 123220 KB Output is correct
9 Correct 2226 ms 123212 KB Output is correct
10 Correct 2388 ms 123472 KB Output is correct
11 Correct 2519 ms 123208 KB Output is correct
12 Correct 6219 ms 123220 KB Output is correct
13 Correct 2632 ms 123220 KB Output is correct
14 Correct 2687 ms 123168 KB Output is correct
15 Correct 3463 ms 123300 KB Output is correct
16 Correct 2680 ms 123340 KB Output is correct
17 Correct 6449 ms 123220 KB Output is correct
18 Correct 5124 ms 123424 KB Output is correct
19 Correct 5159 ms 123220 KB Output is correct
20 Correct 2773 ms 123476 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 80732 KB Output is correct
2 Correct 27 ms 80732 KB Output is correct
3 Correct 28 ms 80580 KB Output is correct
4 Correct 28 ms 80732 KB Output is correct
5 Correct 27 ms 80728 KB Output is correct
6 Correct 27 ms 80732 KB Output is correct
7 Correct 23 ms 80548 KB Output is correct
8 Correct 24 ms 80688 KB Output is correct
9 Correct 29 ms 80732 KB Output is correct
10 Correct 30 ms 80732 KB Output is correct
11 Correct 88 ms 80728 KB Output is correct
12 Correct 86 ms 80508 KB Output is correct
13 Correct 59 ms 80608 KB Output is correct
14 Correct 32 ms 80728 KB Output is correct
15 Correct 37 ms 80764 KB Output is correct
16 Correct 19 ms 80732 KB Output is correct
17 Correct 19 ms 80628 KB Output is correct
18 Correct 20 ms 80476 KB Output is correct
19 Correct 19 ms 80476 KB Output is correct
20 Correct 19 ms 80476 KB Output is correct
21 Correct 22 ms 80476 KB Output is correct
22 Correct 21 ms 80476 KB Output is correct
23 Correct 2665 ms 123088 KB Output is correct
24 Correct 2676 ms 123212 KB Output is correct
25 Correct 3381 ms 123220 KB Output is correct
26 Correct 2688 ms 123220 KB Output is correct
27 Correct 2567 ms 123428 KB Output is correct
28 Correct 4986 ms 123216 KB Output is correct
29 Correct 5083 ms 123428 KB Output is correct
30 Correct 5215 ms 123220 KB Output is correct
31 Correct 2226 ms 123212 KB Output is correct
32 Correct 2388 ms 123472 KB Output is correct
33 Correct 2519 ms 123208 KB Output is correct
34 Correct 6219 ms 123220 KB Output is correct
35 Correct 2632 ms 123220 KB Output is correct
36 Correct 2687 ms 123168 KB Output is correct
37 Correct 3463 ms 123300 KB Output is correct
38 Correct 2680 ms 123340 KB Output is correct
39 Correct 6449 ms 123220 KB Output is correct
40 Correct 5124 ms 123424 KB Output is correct
41 Correct 5159 ms 123220 KB Output is correct
42 Correct 2773 ms 123476 KB Output is correct
43 Correct 11435 ms 100216 KB Output is correct
44 Correct 11429 ms 100180 KB Output is correct
45 Correct 9422 ms 99920 KB Output is correct
46 Correct 11250 ms 104888 KB Output is correct
47 Correct 11242 ms 104572 KB Output is correct
48 Execution timed out 12025 ms 104528 KB Time limit exceeded
49 Halted 0 ms 0 KB -