Submission #100549

#	Time	Username	Problem	Language	Result	Execution time	Memory
100549		Pro_ktmr	Sushi (JOI16_sushi)	C++14	20 / 100	12081 ms	14272 KiB

sushi

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

int N,Q;
int S[400000];
int A[25000],B[25000],P[25000];
set<int> z2;
vector<int> z;
priority_queue<int> s[50002];
int main(){
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N; i++) scanf("%d", S+i);
	for(int i=0; i<Q; i++){
		scanf("%d%d%d", A+i, B+i, P+i);
		A[i]--;
		z2.insert(A[i]);
		z2.insert(B[i]);
	}
	z2.insert(0);
	z2.insert(N);
	for(auto itr=z2.begin(); itr!=z2.end(); itr++) z.push_back(*itr);
	
	for(int i=0; i<N; i++){
		int idx = upper_bound(z.begin(), z.end(), i) - z.begin() - 1;
		s[idx].push(S[i]);
	}
	
	//
	
	for(int q=0; q<Q; q++){
		int start = lower_bound(z.begin(), z.end(), A[q]) - z.begin();
		int fin = lower_bound(z.begin(), z.end(), B[q]) - z.begin();
		int p = P[q];
		if(start < fin){
			for(int i=start; i<fin; i++){
				int tmp = s[i].top();
				if(tmp > p){
					s[i].pop();
					s[i].push(p);
					p = tmp;
				}
			}
		}
		else{
			for(int i=start; i<z.size()-1; i++){
				int tmp = s[i].top();
				if(tmp > p){
					s[i].pop();
					s[i].push(p);
					p = tmp;
				}
			}
			for(int i=0; i<fin; i++){
				int tmp = s[i].top();
				if(tmp > p){
					s[i].pop();
					s[i].push(p);
					p = tmp;
				}
			}
		}
		P[q] = p;
		printf("%d\n", P[q]);
	}
	
	return 0;
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=start; i<z.size()-1; i++){
                     ~^~~~~~~~~~~
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", S+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", A+i, B+i, P+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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