oj.uz

Submission #55908

# Submission time Handle Problem Language Result Execution time Memory
55908 2018-07-09T07:19:12 Z 윤교준(#1564) Sushi (JOI16_sushi) C++11
15 / 100
 3741 ms 78704 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
const bool debug = 0;

const int MAXN = 400005;
const int MAXQ = 25005;
const int SQRN = 655;

struct BUK {
	priority_queue<int, vector<int>, greater<int>> QV;
	priority_queue<int> PQ;
	int A[SQRN];
	int S, E, N;

	int cal(int s, int e, int x) {
		for(int i = s; i <= e; i++)
			if(x < A[i]) swap(A[i], x);
		return x;
	}

	int f(int p, int q, int x) {
		p = max(S, p); q = min(E, q);
		if(p > q) return x;
		if(PQ.top() <= x) return x;
		if(p <= S && E <= q) {
			QV.push(x);
			int ret = PQ.top(); PQ.pop();
			PQ.push(x);
			return ret;
		}

		if(!QV.empty()) {
			for(int i = 0; i < N; i++) {
				if(A[i] <= QV.top()) continue;
				int t = QV.top(); QV.pop();
				A[i] = t;
				QV.push(t);
			}
			priority_queue<int, vector<int>, greater<int>>().swap(QV);
		}

		int ret = cal(p-S, q-S, x);

		priority_queue<int>().swap(PQ);
		for(int i = 0; i < N; i++)
			PQ.push(A[i]);

		return ret;
	}
} buk[SQRN]; int bukn;

int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];

int N, Q;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= Q; i++) cin >> B[i] >> C[i] >> D[i];

	for(int i = 1, s, e;; i++) {
		s = (i-1)*SQRN + 1;
		e = min(N, i*SQRN);
		if(s > e) break;
		
		buk[i].S = s; buk[i].E = e;
		buk[i].N = e-s+1;
		for(int j = s; j <= e; j++) {
			buk[i].A[j-s] = A[j];
			buk[i].PQ.push(A[j]);
		}
		bukn = i;
	}

	if(debug) {
		printf("bukn=%d\n", bukn);
		for(int i = 1; i <= bukn; i++) {
			printf("%d buk : %d %d %d\n", i, buk[i].S, buk[i].E, buk[i].N);
			for(int j = 0; j < buk[i].N; j++) printf("%d ", buk[i].A[j]);
			puts("");
		}
	}

	for(int qi = 1, s, e, x; qi <= Q; qi++) {
		s = B[qi]; e = C[qi]; x = D[qi];

		if(s <= e) {
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(s, e, x);
		} else {
			for(int i = 1; i <= bukn; i++) {
				x = buk[i].f(s, N, x);
			}
			for(int i = 1; i <= bukn; i++)
				x = buk[i].f(1, e, x);
		}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2168 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 2974 ms 78012 KB Output is correct
2 Correct 3276 ms 78012 KB Output is correct
3 Correct 107 ms 78012 KB Output is correct
4 Correct 3327 ms 78112 KB Output is correct
5 Correct 2911 ms 78112 KB Output is correct
6 Correct 3535 ms 78112 KB Output is correct
7 Correct 3493 ms 78112 KB Output is correct
8 Correct 3390 ms 78112 KB Output is correct
9 Correct 121 ms 78112 KB Output is correct
10 Correct 2573 ms 78112 KB Output is correct
11 Correct 119 ms 78112 KB Output is correct
12 Correct 2531 ms 78112 KB Output is correct
13 Correct 3371 ms 78112 KB Output is correct
14 Correct 3317 ms 78532 KB Output is correct
15 Correct 122 ms 78532 KB Output is correct
16 Correct 3292 ms 78704 KB Output is correct
17 Correct 2651 ms 78704 KB Output is correct
18 Correct 3174 ms 78704 KB Output is correct
19 Correct 3741 ms 78704 KB Output is correct
20 Correct 3629 ms 78704 KB Output is correct

Subtask #3
0 / 80.0

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