oj.uz

Submission #134684

# Submission time Handle Problem Language Result Execution time Memory
134684 2019-07-23T07:25:08 Z 송준혁(#3242) Sushi (JOI16_sushi) C++14
5 / 100
 7447 ms 260172 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, Q, Sq=300;
int A[404040];
priority_queue<int> D[1500], P[1500];
priority_queue<int, vector<int>, greater<int>> C[1000];

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++){
		scanf("%d", &A[i]);
		D[i/Sq].push(A[i]);
	}
	while (Q--){
		int S, T, X;
		scanf("%d %d %d", &S, &T, &X);
		int p = S/Sq, q = T/Sq;
		for (int i=max(1,p*Sq); i<min((p+1)*Sq, N+1); i++) C[p].push(A[i]), A[i] = C[p].top(), C[p].pop();
		while (!C[p].empty()) C[p].pop();
		for (int i=max(1,q*Sq); i<min((q+1)*Sq, N+1); i++) C[q].push(A[i]), A[i] = C[q].top(), C[q].pop();
		while (!C[q].empty()) C[q].pop();

		if (S <= T){
			for (int i=S; i<min((p+1)*Sq, T+1); i++) if (X < A[i]) {P[p].push(A[i]), swap(A[i], X), D[p].push(A[i]);}
			for (p++; p<q; p++) {
				while (!P[p].empty() && D[p].top() == P[p].top()) D[p].pop(), P[p].pop();
				C[p].push(X), D[p].push(X);
				X = D[p].top(), D[p].pop();
			}
			for (int i=max(S,q*Sq); i<=T; i++) if (X < A[i]) {P[q].push(A[i]), swap(A[i], X), D[q].push(A[i]);}
		}
		else{
			for (int i=S; i<min((p+1)*Sq, N+1); i++) if (X < A[i]) {P[p].push(A[i]), swap(A[i], X), D[p].push(A[i]);}
			for (p++; p<=N/Sq; p++) {
				while (!P[p].empty() && D[p].top() == P[p].top()) D[p].pop(), P[p].pop();
				C[p].push(X), D[p].push(X);
				X = D[p].top(), D[p].pop();
			}
			for (p=0; p<q; p++) {
				while (!P[p].empty() && D[p].top() == P[p].top()) D[p].pop(), P[p].pop();
				C[p].push(X), D[p].push(X);
				X = D[p].top(), D[p].pop();
			}
			for (int i=max(1,q*Sq); i<=T; i++)  if (X < A[i]) {P[q].push(A[i]), swap(A[i], X), D[q].push(A[i]);}
		}

		printf("%d\n", X);
	}
	return 0;
}
/*
7 100
13
90
35
60
38
64
83
1 4 33
7 1 14
4 5 47
1 7 82
6 1 93
6 5 56
*/

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:12: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:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
sushi.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &S, &T, &X);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 504 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 22 ms 504 KB Output is correct
4 Correct 23 ms 508 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 22 ms 504 KB Output is correct
7 Correct 21 ms 508 KB Output is correct
8 Correct 20 ms 504 KB Output is correct
9 Correct 24 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 67 ms 1276 KB Output is correct
12 Correct 70 ms 1144 KB Output is correct
13 Correct 53 ms 888 KB Output is correct
14 Correct 24 ms 504 KB Output is correct
15 Correct 25 ms 504 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6443 ms 163140 KB Output is correct
2 Correct 6537 ms 163980 KB Output is correct
3 Correct 3522 ms 158852 KB Output is correct
4 Correct 6556 ms 166636 KB Output is correct
5 Correct 6084 ms 260172 KB Output is correct
6 Correct 7258 ms 216880 KB Output is correct
7 Correct 7447 ms 218044 KB Output is correct
8 Correct 7233 ms 218756 KB Output is correct
9 Correct 2933 ms 158896 KB Output is correct
10 Correct 5671 ms 180832 KB Output is correct
11 Runtime error 281 ms 27100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 504 KB Output is correct
2 Correct 23 ms 504 KB Output is correct
3 Correct 22 ms 504 KB Output is correct
4 Correct 23 ms 508 KB Output is correct
5 Correct 22 ms 504 KB Output is correct
6 Correct 22 ms 504 KB Output is correct
7 Correct 21 ms 508 KB Output is correct
8 Correct 20 ms 504 KB Output is correct
9 Correct 24 ms 504 KB Output is correct
10 Correct 23 ms 504 KB Output is correct
11 Correct 67 ms 1276 KB Output is correct
12 Correct 70 ms 1144 KB Output is correct
13 Correct 53 ms 888 KB Output is correct
14 Correct 24 ms 504 KB Output is correct
15 Correct 25 ms 504 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 504 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 6443 ms 163140 KB Output is correct
24 Correct 6537 ms 163980 KB Output is correct
25 Correct 3522 ms 158852 KB Output is correct
26 Correct 6556 ms 166636 KB Output is correct
27 Correct 6084 ms 260172 KB Output is correct
28 Correct 7258 ms 216880 KB Output is correct
29 Correct 7447 ms 218044 KB Output is correct
30 Correct 7233 ms 218756 KB Output is correct
31 Correct 2933 ms 158896 KB Output is correct
32 Correct 5671 ms 180832 KB Output is correct
33 Runtime error 281 ms 27100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -