Submission #134793

#	Time	Username	Problem	Language	Result	Execution time	Memory
134793		onjo0127	Sushi (JOI16_sushi)	C++11	100 / 100	4545 ms	82348 KiB

sushi

#include <bits/stdc++.h>
using namespace std;

const int sn = 632;
int N, X[400009];
priority_queue<int> pq[700], L[700];

inline int geti(int i) { return (i-1) / sn; }

void go(int s, int e, int &x) {
	if(s > e) return;
	int id = geti(s), bs = id*sn+1, be = min(bs + sn - 1, N);
	if(s != bs || e < be) {
		for(int i=bs; i<=be; i++) {
			L[id].push(-X[i]);
			X[i] = -L[id].top();
			L[id].pop();
		}
		L[id] = pq[id] = priority_queue<int>();
		for(int i=s; i<=min(be, e); i++) if(X[i] > x) swap(x, X[i]);
		for(int i=bs; i<=be; i++) pq[id].push(X[i]);
		go(be + 1, e, x);
	}
	else {
		L[id].push(-x);
		pq[id].push(x);
		x = pq[id].top(); pq[id].pop();
		go(be + 1, e, x);
	}
}

int main() {
	int Q; scanf("%d%d",&N,&Q);
	for(int i=1; i<=N; i++) {
		scanf("%d",&X[i]);
		pq[geti(i)].push(X[i]);
	}
	while(Q--) {
		int S, T, P; scanf("%d%d%d",&S,&T,&P);
		int x = P;
		if(S <= T) go(S, T, x);
		else {
			go(S, N, x);
			go(1, T, x);
		}
		printf("%d\n", x);
	}
	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int Q; scanf("%d%d",&N,&Q);
         ~~~~~^~~~~~~~~~~~~~
sushi.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&X[i]);
   ~~~~~^~~~~~~~~~~~
sushi.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S, T, P; scanf("%d%d%d",&S,&T,&P);
                ~~~~~^~~~~~~~~~~~~~~~~~~

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