oj.uz

Submission #56020

# Submission time Handle Problem Language Result Execution time Memory
56020 2018-07-09T11:19:18 Z 정원준(#2100) Sushi (JOI16_sushi) C++11
0 / 100
 1475 ms 141456 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,q,x;
L a[400040];

priority_queue<L>numqueue[1000];
priority_queue<L,vector<L>,greater<L> >queryqueue[1000];

void update(L loc){
	L i;
	for(i=loc*x;i<(loc+1)*x&&i<n;i++)
	{
		if(!queryqueue[loc].empty()&&queryqueue[loc].top()<a[i])
		{
			L temp=a[i];
			a[i]=queryqueue[loc].top();
			queryqueue[loc].pop();
			queryqueue[loc].push(temp);
		}
	}
	
	priority_queue<L,vector<L>,greater<L> >temp;
	swap(temp,queryqueue[loc]);
}

L naive(L s,L e,L num){
	L i;
	for(i=s;i<=e&&i<n;i++)
	{
		if(num<a[i])
		{
			swap(num,a[i]);
		}
	}
	return num;
}

L give(L loc,L num){
	numqueue[loc].push(num);
	queryqueue[loc].push(num);
	L ret=queryqueue[loc].top();
	queryqueue[loc].pop();
	return ret;
}

int main()
{
	scanf("%lld %lld",&n,&q);
	while(x*x<n) x++;
	L i,j;
	for(i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		numqueue[i/x].push(a[i]);
	}
	for(i=1;i<=q;i++)
	{
		L s,e,num;
		scanf("%lld %lld %lld",&s,&e,&num);
		s--;
		e--;
		update(s/x);
		update(e/x);
		if(s<=e)
		{
			if(s/x==e/x)
			{
				printf("%lld\n",naive(s,e,num));
			}
			else
			{
				L temp=naive(s,s/x*x+x-1,num);
				for(j=s/x+1;j<e/x;j++)
				{
					temp=give(j,temp);
				}
				printf("%lld\n",naive(e/x*x,e,temp));
			}
		}
		else
		{
			L temp=naive(s,s/x*x+x-1,num);
			for(j=s/x+1;j<(n-1)/x;j++)
			{
				temp=give(j,temp);
			}
			for(j=0;j<e/x;j++)
			{
				temp=give(j,temp);
			}
			printf("%lld\n",naive(e/x*x,e,temp));
		}
	}
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
telegraph.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
telegraph.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&s,&e,&num);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

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