oj.uz

Submission #444790

# Submission time Handle Problem Language Result Execution time Memory
444790 2021-07-15T10:04:21 Z gustjwkd1007 Sushi (JOI16_sushi) C++14
0 / 100
 2690 ms 77232 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 2056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2690 ms 77232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 2056 KB Output isn't correct
2 Halted 0 ms 0 KB -