Submission #55122

#	Time	Username	Problem	Language	Result	Execution time	Memory
55122		ainta	Sushi (JOI16_sushi)	C++17	100 / 100	7090 ms	95684 KiB

sushi

#include<cstdio>
#include<algorithm>
#include<queue>
#define BB 9
using namespace std;
int n, Q;
struct point {
	int P[1 << BB], SZ;
	vector<int>U;
	priority_queue<int>PQ;
	void Make() {
		int i;
		while (!PQ.empty())PQ.pop();
		for (i = 0; i < SZ; i++) {
			PQ.push(P[i]);
		}
	}
	void init() {
		priority_queue<int>PP;
		for (auto &t : U) {
			PP.push(-t);
		}
		int i;
		for (i = 0; i < SZ; i++) {
			PP.push(-P[i]);
			P[i] = -PP.top();
			PP.pop();
		}
		U.clear();
	}
	int Go(int x) {
		U.push_back(x);
		PQ.push(x);
		int ret = PQ.top();
		PQ.pop();
		return ret;
	}
}w[(400000 >> BB) + 2];
int Do(int b, int e, int x) {
	for (int i = (b >> BB); i <= (e >> BB); i++) {
		int bb = (i << BB), ee = min(((i + 1) << BB) - 1, n - 1);
		if (b <= bb && ee <= e) {
			x = w[i].Go(x);
		}
		else {
			w[i].init();
			bb = max(b, bb)&((1 << BB) - 1);
			ee = min(e, ee)&((1 << BB) - 1);
			for (int j = bb; j <= ee; j++) {
				if (w[i].P[j] > x) {
					swap(w[i].P[j], x);
				}
			}
			w[i].Make();
		}
	}
	return x;
}
int main() {
	int i, b, e, c;
	scanf("%d%d", &n, &Q);
	for (i = 0; i < n; i++) {
		scanf("%d", &w[i >> BB].P[i&((1 << BB) - 1)]);
		w[i >> BB].SZ++;
	}
	for (i = 0; i <= ((n - 1) >> BB); i++)w[i].Make();
	while (Q--) {
		scanf("%d%d%d", &b, &e, &c);
		b--, e--;
		if (b > e) {
			printf("%d\n", Do(0, e, Do(b, n - 1, c)));
		}
		else {
			printf("%d\n", Do(b, e, c));
		}
	}
	return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
telegraph.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i >> BB].P[i&((1 << BB) - 1)]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &b, &e, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80