oj.uz

Submission #1042179

# Submission time Handle Problem Language Result Execution time Memory
1042179 2024-08-02T15:43:12 Z flappybird Sushi (JOI16_sushi) C++17
15 / 100
 12000 ms 194312 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 500
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 - 1, (id + 1) * B); i++) {
		upd[id].emplace(A[i]);
		A[i] = upd[id].top();
		upd[id].pop();
		all[id].emplace(A[i]);
	}
}
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
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7758 ms 194312 KB Output is correct
2 Correct 7600 ms 193620 KB Output is correct
3 Correct 9062 ms 192444 KB Output is correct
4 Correct 7715 ms 191728 KB Output is correct
5 Correct 6713 ms 191884 KB Output is correct
6 Correct 7693 ms 191924 KB Output is correct
7 Correct 7682 ms 191988 KB Output is correct
8 Correct 7470 ms 192000 KB Output is correct
9 Correct 6109 ms 191724 KB Output is correct
10 Correct 6534 ms 191792 KB Output is correct
11 Correct 6194 ms 191824 KB Output is correct
12 Correct 7571 ms 191876 KB Output is correct
13 Correct 7762 ms 191864 KB Output is correct
14 Correct 7603 ms 191784 KB Output is correct
15 Correct 9036 ms 191808 KB Output is correct
16 Correct 7609 ms 191880 KB Output is correct
17 Correct 7603 ms 191872 KB Output is correct
18 Correct 7708 ms 192040 KB Output is correct
19 Correct 7731 ms 191824 KB Output is correct
20 Correct 7266 ms 191840 KB Output is correct

Subtask #3
0 / 80.0

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