oj.uz

Submission #1042177

# Submission time Handle Problem Language Result Execution time Memory
1042177 2024-08-02T15:41:34 Z flappybird Sushi (JOI16_sushi) C++17
15 / 100
 12000 ms 196440 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;
		for (i = 0; i < N; i++) DEBUG(A[i] << bb);
		DEBUG(ln);
	}
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:23:20: warning: statement has no effect [-Wunused-value]
   23 | #define DEBUG(...) 1234
      |                    ^~~~
sushi.cpp:85:27: note: in expansion of macro 'DEBUG'
   85 |   for (i = 0; i < N; i++) DEBUG(A[i] << bb);
      |                           ^~~~~
sushi.cpp:23:20: warning: statement has no effect [-Wunused-value]
   23 | #define DEBUG(...) 1234
      |                    ^~~~
sushi.cpp:86:3: note: in expansion of macro 'DEBUG'
   86 |   DEBUG(ln);
      |   ^~~~~

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7224 ms 192168 KB Output is correct
2 Correct 7181 ms 194896 KB Output is correct
3 Correct 8526 ms 192704 KB Output is correct
4 Correct 7312 ms 196176 KB Output is correct
5 Correct 6538 ms 196212 KB Output is correct
6 Correct 7572 ms 196336 KB Output is correct
7 Correct 7668 ms 196440 KB Output is correct
8 Correct 7510 ms 196348 KB Output is correct
9 Correct 6117 ms 192852 KB Output is correct
10 Correct 6527 ms 194928 KB Output is correct
11 Correct 6078 ms 192896 KB Output is correct
12 Correct 7565 ms 194900 KB Output is correct
13 Correct 8076 ms 196340 KB Output is correct
14 Correct 7998 ms 194708 KB Output is correct
15 Correct 9202 ms 192884 KB Output is correct
16 Correct 7729 ms 196184 KB Output is correct
17 Correct 7792 ms 196304 KB Output is correct
18 Correct 7986 ms 196240 KB Output is correct
19 Correct 7825 ms 196304 KB Output is correct
20 Correct 7132 ms 196208 KB Output is correct

Subtask #3
0 / 80.0

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