oj.uz

Submission #1042169

# Submission time Handle Problem Language Result Execution time Memory
1042169 2024-08-02T15:34:21 Z flappybird Sushi (JOI16_sushi) C++17
0 / 100
 169 ms 205432 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[i].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;
		for (i = l; i <= r; i++) {
			int b = i / B;
			if (i % B && 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));
			}
			else {
				if (upd[b].size()) prop(b);
				//DEBUG('i' << i << bb << A[i] << bb << x << ln);
				if (A[i] > x) {
					all[b].erase(all[b].find(A[i]));
					all[b].insert(x);
					swap(A[i], x);
				}
			}
		}
		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:80:27: note: in expansion of macro 'DEBUG'
   80 |   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:81:3: note: in expansion of macro 'DEBUG'
   81 |   DEBUG(ln);
      |   ^~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

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