Submission #105717

#	Time	Username	Problem	Language	Result	Execution time	Memory
105717		Pro_ktmr	Sushi (JOI16_sushi)	C++14	100 / 100	6059 ms	82888 KiB

sushi

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

int N,Q;
int X[400000];
int S[25000],T[25000],P[25000];
const int B = 633;
priority_queue<int> s[B];
priority_queue<int,vector<int>,greater<int>> memo[B];
int main(){
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N; i++) scanf("%d",X+i);
	for(int i=0; i<Q; i++){
		scanf("%d%d%d", S+i, T+i, P+i);
		S[i]--;
	}

	for(int i=0; i<N; i++) s[i/B].push(X[i]);

	//

	for(int q=0; q<Q; q++){
		int beginB = S[q] / B;
		int endB = (T[q] - 1) / B;

		if(S[q] < T[q]){
			while(!s[beginB].empty()) s[beginB].pop();
			for(int i=beginB*B; i<(beginB+1)*B && i<N; i++){
				memo[beginB].push(X[i]);
				X[i] = memo[beginB].top();
				memo[beginB].pop();
				if(S[q] <= i && i < T[q] && X[i] > P[q]){
					swap(P[q], X[i]);
				}
				s[beginB].push(X[i]);
			}
			while(!memo[beginB].empty()) memo[beginB].pop();

			for(int i=beginB+1; i<endB; i++){
				if(s[i].top() > P[q]){
					int tmp = s[i].top();
					s[i].pop();
					s[i].push(P[q]);
					memo[i].push(P[q]);
					P[q] = tmp;
				}
			}

			if(beginB != endB){
				while(!s[endB].empty()) s[endB].pop();
				for(int i=endB*B; i<(endB+1)*B && i<N; i++){
					memo[endB].push(X[i]);
					X[i] = memo[endB].top();
					memo[endB].pop();
					if(S[q] <= i && i < T[q] && X[i] > P[q]){
						swap(P[q], X[i]);
					}
					s[endB].push(X[i]);
				}
				while(!memo[endB].empty()) memo[endB].pop();
			}
		}
		else{
			while(!s[beginB].empty()) s[beginB].pop();
			for(int i=beginB*B; i<(beginB+1)*B && i<N; i++){
				memo[beginB].push(X[i]);
				X[i] = memo[beginB].top();
				memo[beginB].pop();
				if(S[q] <= i && X[i] > P[q]){
					swap(P[q], X[i]);
				}
				s[beginB].push(X[i]);
			}
			while(!memo[beginB].empty()) memo[beginB].pop();

			for(int i=beginB+1; i<=(N-1)/B; i++){
				if(s[i].top() > P[q]){
					int tmp = s[i].top();
					s[i].pop();
					s[i].push(P[q]);
					memo[i].push(P[q]);
					P[q] = tmp;
				}
			}

			for(int i=0; i<endB; i++){
				if(s[i].top() > P[q]){
					int tmp = s[i].top();
					s[i].pop();
					s[i].push(P[q]);
					memo[i].push(P[q]);
					P[q] = tmp;
				}
			}

			while(!s[endB].empty()) s[endB].pop();
			for(int i=endB*B; i<(endB+1)*B && i<N; i++){
				memo[endB].push(X[i]);
				X[i] = memo[endB].top();
				memo[endB].pop();
				if(i < T[q] && X[i] > P[q]){
					swap(P[q], X[i]);
				}
				s[endB].push(X[i]);
			}
			while(!memo[endB].empty()) memo[endB].pop();
		}

		printf("%d\n", P[q]);
	}

	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:12:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d",X+i);
                         ~~~~~^~~~~~~~~~
sushi.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", S+i, T+i, P+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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