oj.uz

Submission #134647

# Submission time Handle Problem Language Result Execution time Memory
134647 2019-07-23T06:23:33 Z 송준혁(#3242) Sushi (JOI16_sushi) C++14
15 / 100
 2905 ms 63628 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, Q, Sq=800;
int A[404040];
priority_queue<int> D[600];
priority_queue<int, vector<int>, greater<int>> C[600];

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]) swap(A[i], X);
			for (p++; p<q; p++) 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]) swap(A[i], X);
		}
		else{
			for (int i=S; i<min((p+1)*Sq, N+1); i++) if (X < A[i]) swap(A[i], X);
			for (p++; p<=N/Sq; p++) C[p].push(X), D[p].push(X), X = D[p].top(), D[p].pop();
			for (p=0; p<q; p++) 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]) swap(A[i], X);
		}

		printf("%d\n", X);
	}
	return 0;
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 380 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 2824 ms 61992 KB Output is correct
2 Correct 2905 ms 63348 KB Output is correct
3 Correct 1440 ms 62704 KB Output is correct
4 Correct 2859 ms 63500 KB Output is correct
5 Correct 2212 ms 63580 KB Output is correct
6 Correct 2801 ms 63368 KB Output is correct
7 Correct 2836 ms 63628 KB Output is correct
8 Correct 2827 ms 63488 KB Output is correct
9 Correct 1319 ms 62324 KB Output is correct
10 Correct 2132 ms 63264 KB Output is correct
11 Correct 1277 ms 62188 KB Output is correct
12 Correct 2302 ms 63080 KB Output is correct
13 Correct 2841 ms 63048 KB Output is correct
14 Correct 2831 ms 62960 KB Output is correct
15 Correct 1267 ms 62424 KB Output is correct
16 Correct 2838 ms 63232 KB Output is correct
17 Correct 2366 ms 63080 KB Output is correct
18 Correct 2849 ms 63148 KB Output is correct
19 Correct 2810 ms 63084 KB Output is correct
20 Correct 2604 ms 63288 KB Output is correct

Subtask #3
0 / 80.0

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