oj.uz

Submission #56026

# Submission time Handle Problem Language Result Execution time Memory
56026 2018-07-09T11:46:02 Z 정원준(#2100) Sushi (JOI16_sushi) C++11
15 / 100
 6625 ms 143488 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]);
		}
	}
	priority_queue<L>temp;
	swap(temp,numqueue[s/x]);
	for(i=s/x;i<s/x+x&&i<n;i++)
	{
		numqueue[s/x].push(a[i]);
	}
	return num;
}

L give(L loc,L num){
	queryqueue[loc].push(num);
	numqueue[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:57: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:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
telegraph.cpp:68: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 22 ms 504 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 5476 ms 143328 KB Output is correct
2 Correct 5907 ms 143328 KB Output is correct
3 Correct 3181 ms 143328 KB Output is correct
4 Correct 5486 ms 143328 KB Output is correct
5 Correct 5138 ms 143328 KB Output is correct
6 Correct 6502 ms 143328 KB Output is correct
7 Correct 6267 ms 143328 KB Output is correct
8 Correct 6257 ms 143456 KB Output is correct
9 Correct 3283 ms 143456 KB Output is correct
10 Correct 4843 ms 143456 KB Output is correct
11 Correct 3152 ms 143456 KB Output is correct
12 Correct 4974 ms 143456 KB Output is correct
13 Correct 6008 ms 143456 KB Output is correct
14 Correct 6139 ms 143456 KB Output is correct
15 Correct 3191 ms 143456 KB Output is correct
16 Correct 6545 ms 143456 KB Output is correct
17 Correct 5462 ms 143456 KB Output is correct
18 Correct 6557 ms 143456 KB Output is correct
19 Correct 6124 ms 143480 KB Output is correct
20 Correct 6625 ms 143488 KB Output is correct

Subtask #3
0 / 80.0

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