Submission #251035

#	Time	Username	Problem	Language	Result	Execution time	Memory
251035		gustjwkd1007	Sushi (JOI16_sushi)	C++14	5 / 100	3850 ms	262148 KiB

sushi

#include <bits/stdc++.h>
#define buc 3
using namespace std;
int n,q;
int input[410000];
priority_queue <int> pq[410000/buc];
priority_queue <int,vector <int>,greater<int> > ms[410000/buc];
void showpq(int ind)
{
	vector <int> now;
	while(!pq[ind].empty())
	{
		printf("%d ",pq[ind].top());
		now.push_back(pq[ind].top());
		pq[ind].pop();
	}
	for(int x : now)
		pq[ind].push(x);
	printf("\n");
}
void show()
{
	for(int i=0;i<n;i+=buc)
	{
		printf("%d : ",i);
		showpq(i/buc);
	}
}
void updatepq(int ind)
{
	while(!pq[ind].empty())
		pq[ind].pop();
	for(int i=ind*buc;i<(ind+1)*buc;i++)
		pq[ind].push(input[i]);
}
void propa(int ind)
{
	for(int i=ind*buc;i<(ind+1)*buc;i++)
	{
		ms[ind].push(input[i]);
		input[i]=ms[ind].top();
		ms[ind].pop();
	}
	while(!ms[ind].empty())
		ms[ind].pop();
	updatepq(ind);
}
int query(int st,int fin,int p)
{
	if(st%buc)
	{
		propa(st/buc);
		for(;st%buc&&st<=fin;st++)
		{
			if(input[st]>p)
				swap(p,input[st]);
		}
		updatepq((st-1)/buc);
	}
	for(;st+buc-1<=fin;st+=buc)
	{
		ms[st/buc].push(p);
		pq[st/buc].push(p);
		p=pq[st/buc].top();
		pq[st/buc].pop();
	}
	if(st<=fin)
	{
		propa(st/buc);
		for(;st<=fin;st++)
		{
			if(input[st]>p)
				swap(p,input[st]);
		}
		updatepq(fin/buc);
	}
	return p;
}
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&input[i]);
		pq[i/buc].push(input[i]);
	}
	int s,t,p;
	for(int i=0;i<q;i++)
	{
		scanf("%d %d %d",&s,&t,&p);
		if(s<=t)
			printf("%d\n",query(s-1,t-1,p));
		else
			printf("%d\n",query(0,t-1,query(s-1,n-1,p)));
//		for(int j=0;j<n;j++)
//			printf("%d ",input[j]);
//		printf("\n");
//		show();
	}
}

Compilation message (stderr)

sushi.cpp: In function 'int main()':
sushi.cpp:81: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:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&input[i]);
   ~~~~~^~~~~~~~~~~~~~~~
sushi.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&t,&p);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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