Submission #56023

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56023	2018-07-09T11:28:20 Z	정원준(#2100)	Sushi (JOI16_sushi)	C++11	15 / 100	5049 ms	143700 KB

sushi

#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=numqueue[loc].top();
	numqueue[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	376 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4944 ms	143332 KB	Output is correct
2	Correct	4160 ms	143332 KB	Output is correct
3	Correct	2405 ms	143332 KB	Output is correct
4	Correct	4523 ms	143344 KB	Output is correct
5	Correct	4041 ms	143504 KB	Output is correct
6	Correct	4955 ms	143536 KB	Output is correct
7	Correct	4745 ms	143580 KB	Output is correct
8	Correct	4369 ms	143580 KB	Output is correct
9	Correct	2452 ms	143580 KB	Output is correct
10	Correct	4037 ms	143580 KB	Output is correct
11	Correct	2357 ms	143580 KB	Output is correct
12	Correct	3833 ms	143580 KB	Output is correct
13	Correct	4121 ms	143684 KB	Output is correct
14	Correct	4164 ms	143684 KB	Output is correct
15	Correct	2475 ms	143684 KB	Output is correct
16	Correct	4777 ms	143684 KB	Output is correct
17	Correct	4369 ms	143684 KB	Output is correct
18	Correct	4566 ms	143700 KB	Output is correct
19	Correct	5049 ms	143700 KB	Output is correct
20	Correct	4559 ms	143700 KB	Output is correct

Subtask #3

0 / 80.0

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