oj.uz

Submission #202438

# Submission time Handle Problem Language Result Execution time Memory
202438 2020-02-16T05:59:04 Z ho94949 Sushi (JOI16_sushi) C++17
100 / 100
 9053 ms 83064 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 400000;
const int BUCKET = 625;
const int BUCKET_CNT = 640;
int arr[MAXN];
priority_queue<int> pq[BUCKET_CNT];
priority_queue<int, vector<int>, greater<int> > lazy[BUCKET_CNT];
int N, Q;
void init()
{
	for(int i=0; i<BUCKET_CNT; ++i)
	{
		for(int j=0; j<BUCKET; ++j)
		{
			if(i*BUCKET+j >= N) return;
			pq[i].push(arr[i*BUCKET+j]);
		}
	}
}
void bucket_fixup(int bucket_idx)
{
	for(int i=bucket_idx*BUCKET; i<min(N, (bucket_idx+1)*BUCKET); ++i)
	{
		lazy[bucket_idx].push(arr[i]);
		arr[i] = lazy[bucket_idx].top();
		lazy[bucket_idx].pop();
	}
	while(!lazy[bucket_idx].empty()) lazy[bucket_idx].pop();
}
int naive(int l, int r, int v)
{
	int bucket_idx = l/BUCKET;
	bucket_fixup(l/BUCKET);
	for(int i=l; i<=r; ++i)
		if(arr[i] > v)
			swap(arr[i], v);
	while(!pq[bucket_idx].empty()) pq[bucket_idx].pop();
	for(int i=bucket_idx*BUCKET; i<min(N, (bucket_idx+1)*BUCKET); ++i)
		pq[bucket_idx].push(arr[i]);
	return v;
}
int Query(int l, int r, int v)
{
	int l_bucket = l/BUCKET, r_bucket = r/BUCKET;
	if(l_bucket == r_bucket)
		return naive(l, r, v);
	
	v = naive(l, l_bucket*BUCKET + BUCKET-1, v);
	for(int i=l_bucket+1; i<=r_bucket-1; ++i)
	{
		pq[i].push(v);
		lazy[i].push(v);
		v = pq[i].top(); pq[i].pop();
	}
	v = naive(r_bucket*BUCKET, r, v);
	return v;
}
int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N; ++i)
		scanf("%d", &arr[i]);
	init();
	vector<tuple<int, int, int> > queries;
	for(int i=0; i<Q; ++i)
	{
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		--a; --b;
		if(a<=b)
		{
			printf("%d\n", Query(a, b, c));
		}
		else
		{
			int q = Query(a, N-1, c);
			printf("%d\n", Query(0, b, q));
		}
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:61: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:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
sushi.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d%d%d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 508 KB Output is correct
2 Correct 223 ms 504 KB Output is correct
3 Correct 225 ms 504 KB Output is correct
4 Correct 220 ms 648 KB Output is correct
5 Correct 221 ms 376 KB Output is correct
6 Correct 221 ms 508 KB Output is correct
7 Correct 103 ms 504 KB Output is correct
8 Correct 97 ms 380 KB Output is correct
9 Correct 227 ms 504 KB Output is correct
10 Correct 222 ms 636 KB Output is correct
11 Correct 216 ms 504 KB Output is correct
12 Correct 218 ms 632 KB Output is correct
13 Correct 230 ms 528 KB Output is correct
14 Correct 290 ms 504 KB Output is correct
15 Correct 287 ms 632 KB Output is correct
16 Correct 105 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 380 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5286 ms 82604 KB Output is correct
2 Correct 5519 ms 81360 KB Output is correct
3 Correct 2480 ms 79328 KB Output is correct
4 Correct 5338 ms 82644 KB Output is correct
5 Correct 4397 ms 82672 KB Output is correct
6 Correct 5518 ms 82708 KB Output is correct
7 Correct 5379 ms 83064 KB Output is correct
8 Correct 5290 ms 82740 KB Output is correct
9 Correct 2120 ms 79152 KB Output is correct
10 Correct 4462 ms 81524 KB Output is correct
11 Correct 2228 ms 79404 KB Output is correct
12 Correct 4495 ms 81460 KB Output is correct
13 Correct 5424 ms 82884 KB Output is correct
14 Correct 5471 ms 81380 KB Output is correct
15 Correct 2506 ms 79412 KB Output is correct
16 Correct 5324 ms 82892 KB Output is correct
17 Correct 4383 ms 82716 KB Output is correct
18 Correct 5365 ms 82744 KB Output is correct
19 Correct 5396 ms 82576 KB Output is correct
20 Correct 5266 ms 82552 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 508 KB Output is correct
2 Correct 223 ms 504 KB Output is correct
3 Correct 225 ms 504 KB Output is correct
4 Correct 220 ms 648 KB Output is correct
5 Correct 221 ms 376 KB Output is correct
6 Correct 221 ms 508 KB Output is correct
7 Correct 103 ms 504 KB Output is correct
8 Correct 97 ms 380 KB Output is correct
9 Correct 227 ms 504 KB Output is correct
10 Correct 222 ms 636 KB Output is correct
11 Correct 216 ms 504 KB Output is correct
12 Correct 218 ms 632 KB Output is correct
13 Correct 230 ms 528 KB Output is correct
14 Correct 290 ms 504 KB Output is correct
15 Correct 287 ms 632 KB Output is correct
16 Correct 105 ms 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 380 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5286 ms 82604 KB Output is correct
24 Correct 5519 ms 81360 KB Output is correct
25 Correct 2480 ms 79328 KB Output is correct
26 Correct 5338 ms 82644 KB Output is correct
27 Correct 4397 ms 82672 KB Output is correct
28 Correct 5518 ms 82708 KB Output is correct
29 Correct 5379 ms 83064 KB Output is correct
30 Correct 5290 ms 82740 KB Output is correct
31 Correct 2120 ms 79152 KB Output is correct
32 Correct 4462 ms 81524 KB Output is correct
33 Correct 2228 ms 79404 KB Output is correct
34 Correct 4495 ms 81460 KB Output is correct
35 Correct 5424 ms 82884 KB Output is correct
36 Correct 5471 ms 81380 KB Output is correct
37 Correct 2506 ms 79412 KB Output is correct
38 Correct 5324 ms 82892 KB Output is correct
39 Correct 4383 ms 82716 KB Output is correct
40 Correct 5365 ms 82744 KB Output is correct
41 Correct 5396 ms 82576 KB Output is correct
42 Correct 5266 ms 82552 KB Output is correct
43 Correct 6317 ms 12484 KB Output is correct
44 Correct 6280 ms 12376 KB Output is correct
45 Correct 3365 ms 8972 KB Output is correct
46 Correct 6246 ms 12580 KB Output is correct
47 Correct 6249 ms 12808 KB Output is correct
48 Correct 6220 ms 12584 KB Output is correct
49 Correct 6793 ms 12672 KB Output is correct
50 Correct 6681 ms 12732 KB Output is correct
51 Correct 6750 ms 12792 KB Output is correct
52 Correct 9053 ms 19152 KB Output is correct
53 Correct 8797 ms 18856 KB Output is correct
54 Correct 8241 ms 19056 KB Output is correct
55 Correct 8936 ms 19112 KB Output is correct
56 Correct 8968 ms 19048 KB Output is correct
57 Correct 8983 ms 19196 KB Output is correct
58 Correct 4576 ms 14768 KB Output is correct
59 Correct 4632 ms 14584 KB Output is correct
60 Correct 4688 ms 82908 KB Output is correct
61 Correct 5459 ms 83032 KB Output is correct
62 Correct 5473 ms 82768 KB Output is correct
63 Correct 5427 ms 82972 KB Output is correct
64 Correct 2440 ms 8836 KB Output is correct
65 Correct 3308 ms 45184 KB Output is correct
66 Correct 3274 ms 45200 KB Output is correct
67 Correct 7277 ms 68736 KB Output is correct
68 Correct 8154 ms 68696 KB Output is correct
69 Correct 8154 ms 68472 KB Output is correct
70 Correct 8064 ms 68528 KB Output is correct