Submission #203833

#	Time	Username	Problem	Language	Result	Execution time	Memory
203833		youngyojun	Sushi (JOI16_sushi)	C++11	100 / 100	5106 ms	82544 KiB

sushi

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 400005;
const int MAXQ = 25005;
const int SQRN = 655;
 
struct BUK {
	priority_queue<int, vector<int>, greater<int>> QV;
	priority_queue<int> PQ;
	int A[SQRN];
	int S, E, N;
 
	int cal(int s, int e, int x) {
		for(int i = s; i <= e; i++)
			if(x < A[i]) swap(A[i], x);
		return x;
	}
 
	int f(int p, int q, int x) {
		p = max(S, p); q = min(E, q);
		if(p > q) return x;
		if(PQ.top() <= x) return x;
		if(p <= S && E <= q) {
			QV.push(x);
			int ret = PQ.top(); PQ.pop();
			PQ.push(x);
			return ret;
		}
 
		if(!QV.empty()) {
			for(int i = 0; i < N; i++) {
				if(A[i] <= QV.top()) continue;
				int t = QV.top(); QV.pop();
				QV.push(A[i]);
				A[i] = t;
			}
			for(; !QV.empty(); QV.pop());
		}
 
		int ret = cal(p-S, q-S, x);
 
		for(; !PQ.empty(); PQ.pop());
		for(int i = 0; i < N; i++)
			PQ.push(A[i]);
 
		return ret;
	}
} buk[SQRN]; int bukn;
 
int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];
 
int N, Q;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
 
	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= Q; i++) cin >> B[i] >> C[i] >> D[i];
 
	for(int i = 1, s, e;; i++) {
		s = (i-1)*SQRN + 1;
		e = min(N, i*SQRN);
		if(s > e) break;
		
		buk[i].S = s; buk[i].E = e;
		buk[i].N = e-s+1;
		for(int j = s; j <= e; j++) {
			buk[i].A[j-s] = A[j];
			buk[i].PQ.push(A[j]);
		}
		bukn = i;
	}
 
	for(int qi = 1, s, e, x; qi <= Q; qi++) {
		s = B[qi]; e = C[qi]; x = D[qi];
 
		if(s <= e) {
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(s, e, x);
		} else {
			for(int i = 1; i <= bukn; i++) {
				x = buk[i].f(s, N, x);
			}
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(1, e, x);
		}

		cout << x << '\n';
	}
	return 0;
}

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