oj.uz

Submission #157759

# Submission time Handle Problem Language Result Execution time Memory
157759 2019-10-12T19:46:15 Z TadijaSebez Sushi (JOI16_sushi) C++11
100 / 100
 6604 ms 6876 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=400050;
const int S=447;
const int M=N/S+1;
const int Q=25050;
priority_queue<pair<int,int>> st[M];
int a[N],n,q;
bool mark[N];
int Push(int B, int x)
{
	st[B].push({x,0});
	int p;tie(x,p)=st[B].top();
	st[B].pop();
	if(p) mark[-p]=1;
	return x;
}
void BuildBlock(int B, int l, int r){ for(int i=l;i<=r;i++) st[B].push({a[i],-i}),mark[i]=0;}
void BreakBlock(int B)
{
	int l=B*S,r=min((B+1)*S,n)-1;
	for(int i=r;i>=l;i--)
	{
		if(mark[i])
		{
			int x,y;
			do
			{
				tie(x,y)=st[B].top();
				st[B].pop();
			}while(-y>i);
			a[i]=x;
			if(y) mark[-y]=1;
		}
	}
	while(st[B].size()) st[B].pop();
}
int Push(int B, int l, int r, int x)
{
	BreakBlock(B);
	for(int i=l;i<=r;i++) if(a[i]>x) swap(a[i],x);
	BuildBlock(B,B*S,min((B+1)*S,n)-1);
	return x;
}
void BuildAll(){ for(int l=0;l<n;l+=S) BuildBlock(l/S,l,min(l+S,n)-1);}
int Query(int l, int r, int x)
{
	int L=l/S,R=r/S;
	if(L==R)
	{
		x=Push(L,l,r,x);
	}
	else
	{
		x=Push(L,l,L*S+S-1,x);
		for(int i=L+1;i<R;i++) x=Push(i,x);
		x=Push(R,R*S,r,x);
	}
	return x;
}
int main()
{
	scanf("%i %i",&n,&q);
	for(int i=0;i<n;i++) scanf("%i",&a[i]);
	BuildAll();
	while(q--)
	{
		int l,r,x;
		scanf("%i %i %i",&l,&r,&x);
		l--;r--;
		if(l<=r) x=Query(l,r,x);
		else x=Query(0,r,Query(l,n-1,x));
		printf("%i\n",x);
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
sushi.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&l,&r,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 504 KB Output is correct
2 Correct 203 ms 504 KB Output is correct
3 Correct 199 ms 376 KB Output is correct
4 Correct 196 ms 616 KB Output is correct
5 Correct 202 ms 596 KB Output is correct
6 Correct 203 ms 504 KB Output is correct
7 Correct 148 ms 376 KB Output is correct
8 Correct 149 ms 504 KB Output is correct
9 Correct 201 ms 628 KB Output is correct
10 Correct 197 ms 512 KB Output is correct
11 Correct 192 ms 504 KB Output is correct
12 Correct 196 ms 492 KB Output is correct
13 Correct 210 ms 512 KB Output is correct
14 Correct 263 ms 488 KB Output is correct
15 Correct 259 ms 732 KB Output is correct
16 Correct 85 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 392 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4348 ms 6756 KB Output is correct
2 Correct 4374 ms 6752 KB Output is correct
3 Correct 4130 ms 6488 KB Output is correct
4 Correct 4278 ms 6796 KB Output is correct
5 Correct 3084 ms 6780 KB Output is correct
6 Correct 4423 ms 6756 KB Output is correct
7 Correct 4386 ms 6876 KB Output is correct
8 Correct 4319 ms 6716 KB Output is correct
9 Correct 3773 ms 6120 KB Output is correct
10 Correct 3237 ms 6468 KB Output is correct
11 Correct 3765 ms 6128 KB Output is correct
12 Correct 3186 ms 6168 KB Output is correct
13 Correct 4321 ms 6416 KB Output is correct
14 Correct 4361 ms 6332 KB Output is correct
15 Correct 4064 ms 6084 KB Output is correct
16 Correct 4315 ms 6332 KB Output is correct
17 Correct 3091 ms 6304 KB Output is correct
18 Correct 4400 ms 6188 KB Output is correct
19 Correct 4363 ms 6376 KB Output is correct
20 Correct 4331 ms 6368 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 504 KB Output is correct
2 Correct 203 ms 504 KB Output is correct
3 Correct 199 ms 376 KB Output is correct
4 Correct 196 ms 616 KB Output is correct
5 Correct 202 ms 596 KB Output is correct
6 Correct 203 ms 504 KB Output is correct
7 Correct 148 ms 376 KB Output is correct
8 Correct 149 ms 504 KB Output is correct
9 Correct 201 ms 628 KB Output is correct
10 Correct 197 ms 512 KB Output is correct
11 Correct 192 ms 504 KB Output is correct
12 Correct 196 ms 492 KB Output is correct
13 Correct 210 ms 512 KB Output is correct
14 Correct 263 ms 488 KB Output is correct
15 Correct 259 ms 732 KB Output is correct
16 Correct 85 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 392 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 4348 ms 6756 KB Output is correct
24 Correct 4374 ms 6752 KB Output is correct
25 Correct 4130 ms 6488 KB Output is correct
26 Correct 4278 ms 6796 KB Output is correct
27 Correct 3084 ms 6780 KB Output is correct
28 Correct 4423 ms 6756 KB Output is correct
29 Correct 4386 ms 6876 KB Output is correct
30 Correct 4319 ms 6716 KB Output is correct
31 Correct 3773 ms 6120 KB Output is correct
32 Correct 3237 ms 6468 KB Output is correct
33 Correct 3765 ms 6128 KB Output is correct
34 Correct 3186 ms 6168 KB Output is correct
35 Correct 4321 ms 6416 KB Output is correct
36 Correct 4361 ms 6332 KB Output is correct
37 Correct 4064 ms 6084 KB Output is correct
38 Correct 4315 ms 6332 KB Output is correct
39 Correct 3091 ms 6304 KB Output is correct
40 Correct 4400 ms 6188 KB Output is correct
41 Correct 4363 ms 6376 KB Output is correct
42 Correct 4331 ms 6368 KB Output is correct
43 Correct 4166 ms 6436 KB Output is correct
44 Correct 4164 ms 6380 KB Output is correct
45 Correct 4046 ms 6096 KB Output is correct
46 Correct 4157 ms 6380 KB Output is correct
47 Correct 4153 ms 6316 KB Output is correct
48 Correct 4316 ms 6396 KB Output is correct
49 Correct 4751 ms 6348 KB Output is correct
50 Correct 4686 ms 6272 KB Output is correct
51 Correct 4697 ms 6268 KB Output is correct
52 Correct 5912 ms 6384 KB Output is correct
53 Correct 5724 ms 6368 KB Output is correct
54 Correct 5983 ms 6364 KB Output is correct
55 Correct 6604 ms 6312 KB Output is correct
56 Correct 6554 ms 6328 KB Output is correct
57 Correct 6487 ms 6352 KB Output is correct
58 Correct 3441 ms 6284 KB Output is correct
59 Correct 3376 ms 6284 KB Output is correct
60 Correct 3353 ms 6364 KB Output is correct
61 Correct 4439 ms 6452 KB Output is correct
62 Correct 4425 ms 6496 KB Output is correct
63 Correct 4368 ms 6604 KB Output is correct
64 Correct 3661 ms 6372 KB Output is correct
65 Correct 2944 ms 6456 KB Output is correct
66 Correct 2908 ms 6456 KB Output is correct
67 Correct 5294 ms 6404 KB Output is correct
68 Correct 6315 ms 6548 KB Output is correct
69 Correct 6345 ms 6472 KB Output is correct
70 Correct 6215 ms 6504 KB Output is correct