Submission #444790

#	Time	Username	Problem	Language	Result	Execution time	Memory
444790		gustjwkd1007	Sushi (JOI16_sushi)	C++14	0 / 100	2690 ms	77232 KiB

sushi

#include <bits/stdc++.h>
#define MAX_N 650
#define INF 1e9+7
using namespace std;
struct bucket{
	priority_queue<int> mx;
	priority_queue<int,vector<int>,greater<int>> mn;
	int A[MAX_N];
	bucket(){
		for(int i=0;i<MAX_N;i++)
			A[i]=INF;
	}
	int update(int in){
		mx.push(in);
		mn.push(in);
		int re= mx.top();
		mx.pop();
		return re;
	}
	void show(){
		for(int i=0;i<MAX_N&&!mn.empty();i++){
			mn.push(A[i]);
			A[i]=mn.top();
			mn.pop();
		}
		while(!mn.empty())
			mn.pop();
		while(!mx.empty())
			mx.pop();
		for(int i=0;i<MAX_N;i++)
			mx.push(A[i]);
	}
	int direct_update(int s,int e,int in){
		show();
		for(int i=s;i<=e;i++)if(A[i]>in)
			swap(A[i],in);
		return in;
	}
}input[MAX_N];
int n,q;
int query(int s,int t,int p){
	if(s/MAX_N == t/MAX_N)
		p = input[s/MAX_N].direct_update(s%MAX_N,t%MAX_N,p);
	else{
		int ind =s/MAX_N+1;
		p = input[ind-1].direct_update(s%MAX_N,MAX_N-1,p);
		for(;ind<t/MAX_N;ind++)
			p = input[ind].update(p);
		p = input[ind].direct_update(0,t%MAX_N,p);
	}
	return p;
}
int main(){
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++)
		scanf("%d",&input[i/MAX_N].A[i%MAX_N]);
	int s,t,p;
	while(q--){
		scanf("%d %d %d",&s,&t,&p);
		s--;
		t--;
		if(s>t){
			p = query(s,n-1,p);
			p = query(0,t,p);
		}
		else
			p = query(s,t,p);
		printf("%d\n",p);
	}
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d %d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d",&input[i/MAX_N].A[i%MAX_N]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sushi.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d %d %d",&s,&t,&p);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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