oj.uz

Submission #251036

# Submission time Handle Problem Language Result Execution time Memory
251036 2020-07-20T01:18:01 Z gustjwkd1007 Sushi (JOI16_sushi) C++14
100 / 100
 10346 ms 82532 KB 
#include <bits/stdc++.h>
#define buc 632
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

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

# Verdict Execution time Memory Grader output
1 Correct 370 ms 632 KB Output is correct
2 Correct 363 ms 504 KB Output is correct
3 Correct 366 ms 632 KB Output is correct
4 Correct 367 ms 384 KB Output is correct
5 Correct 369 ms 440 KB Output is correct
6 Correct 365 ms 384 KB Output is correct
7 Correct 166 ms 504 KB Output is correct
8 Correct 164 ms 504 KB Output is correct
9 Correct 365 ms 632 KB Output is correct
10 Correct 367 ms 504 KB Output is correct
11 Correct 364 ms 504 KB Output is correct
12 Correct 363 ms 588 KB Output is correct
13 Correct 386 ms 576 KB Output is correct
14 Correct 422 ms 384 KB Output is correct
15 Correct 420 ms 632 KB Output is correct
16 Correct 175 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4118 ms 82056 KB Output is correct
2 Correct 4320 ms 80788 KB Output is correct
3 Correct 2422 ms 78436 KB Output is correct
4 Correct 4239 ms 82096 KB Output is correct
5 Correct 3693 ms 81912 KB Output is correct
6 Correct 4607 ms 81888 KB Output is correct
7 Correct 4556 ms 81912 KB Output is correct
8 Correct 4582 ms 82052 KB Output is correct
9 Correct 2219 ms 78544 KB Output is correct
10 Correct 3511 ms 80748 KB Output is correct
11 Correct 2013 ms 78500 KB Output is correct
12 Correct 3589 ms 80760 KB Output is correct
13 Correct 4161 ms 82008 KB Output is correct
14 Correct 4156 ms 80544 KB Output is correct
15 Correct 2423 ms 78540 KB Output is correct
16 Correct 4142 ms 82160 KB Output is correct
17 Correct 3608 ms 81912 KB Output is correct
18 Correct 4678 ms 82340 KB Output is correct
19 Correct 4646 ms 82164 KB Output is correct
20 Correct 4519 ms 82532 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 632 KB Output is correct
2 Correct 363 ms 504 KB Output is correct
3 Correct 366 ms 632 KB Output is correct
4 Correct 367 ms 384 KB Output is correct
5 Correct 369 ms 440 KB Output is correct
6 Correct 365 ms 384 KB Output is correct
7 Correct 166 ms 504 KB Output is correct
8 Correct 164 ms 504 KB Output is correct
9 Correct 365 ms 632 KB Output is correct
10 Correct 367 ms 504 KB Output is correct
11 Correct 364 ms 504 KB Output is correct
12 Correct 363 ms 588 KB Output is correct
13 Correct 386 ms 576 KB Output is correct
14 Correct 422 ms 384 KB Output is correct
15 Correct 420 ms 632 KB Output is correct
16 Correct 175 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 4118 ms 82056 KB Output is correct
24 Correct 4320 ms 80788 KB Output is correct
25 Correct 2422 ms 78436 KB Output is correct
26 Correct 4239 ms 82096 KB Output is correct
27 Correct 3693 ms 81912 KB Output is correct
28 Correct 4607 ms 81888 KB Output is correct
29 Correct 4556 ms 81912 KB Output is correct
30 Correct 4582 ms 82052 KB Output is correct
31 Correct 2219 ms 78544 KB Output is correct
32 Correct 3511 ms 80748 KB Output is correct
33 Correct 2013 ms 78500 KB Output is correct
34 Correct 3589 ms 80760 KB Output is correct
35 Correct 4161 ms 82008 KB Output is correct
36 Correct 4156 ms 80544 KB Output is correct
37 Correct 2423 ms 78540 KB Output is correct
38 Correct 4142 ms 82160 KB Output is correct
39 Correct 3608 ms 81912 KB Output is correct
40 Correct 4678 ms 82340 KB Output is correct
41 Correct 4646 ms 82164 KB Output is correct
42 Correct 4519 ms 82532 KB Output is correct
43 Correct 8421 ms 12500 KB Output is correct
44 Correct 8235 ms 12304 KB Output is correct
45 Correct 4358 ms 8772 KB Output is correct
46 Correct 8247 ms 12324 KB Output is correct
47 Correct 8260 ms 12400 KB Output is correct
48 Correct 7700 ms 12484 KB Output is correct
49 Correct 8631 ms 12488 KB Output is correct
50 Correct 8626 ms 12684 KB Output is correct
51 Correct 8550 ms 12292 KB Output is correct
52 Correct 10240 ms 19052 KB Output is correct
53 Correct 9931 ms 18604 KB Output is correct
54 Correct 9259 ms 18724 KB Output is correct
55 Correct 10346 ms 18404 KB Output is correct
56 Correct 10280 ms 18724 KB Output is correct
57 Correct 10292 ms 18904 KB Output is correct
58 Correct 4268 ms 14336 KB Output is correct
59 Correct 6068 ms 14464 KB Output is correct
60 Correct 5803 ms 81872 KB Output is correct
61 Correct 6834 ms 82348 KB Output is correct
62 Correct 6854 ms 81956 KB Output is correct
63 Correct 6810 ms 82076 KB Output is correct
64 Correct 3083 ms 8776 KB Output is correct
65 Correct 4202 ms 45148 KB Output is correct
66 Correct 4144 ms 44836 KB Output is correct
67 Correct 7696 ms 68416 KB Output is correct
68 Correct 9009 ms 68144 KB Output is correct
69 Correct 8994 ms 68284 KB Output is correct
70 Correct 8949 ms 68504 KB Output is correct