oj.uz

Submission #199464

# Submission time Handle Problem Language Result Execution time Memory
199464 2020-02-01T13:15:01 Z dennisstar Sushi (JOI16_sushi) C++17
15 / 100
 5661 ms 10760 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;

const int sz = 600;

int N, M, Q, X[400010];
vector<pii> B[1010]; priority_queue<int> S[1010];

inline void make(int t) {
	B[t].clear(); while(!S[t].empty()) S[t].pop();
	int ub=min((t+1)*sz, N);
	for (int i=t*sz; i<ub; i++) B[t].eb(X[i], i);
	sort(all(B[t])); reverse(all(B[t]));
	for (auto &i:B[t]) S[t].em(i.fi);
}

inline void upd(int t) {
	for (auto &i:B[t]) { i.fi=S[t].top(); X[i.se]=i.fi; S[t].pop(); }
	for (auto &i:B[t]) S[t].em(i.fi);
}

inline int sol(int t, int p) {
	S[t].em(p); p=S[t].top(); S[t].pop();
	return p;
}

inline int f(int s, int e, int p) {
	int st=s/sz, et=e/sz;
	upd(st); upd(et);
	if (st==et) { for (int i=s; i<=e; i++) if (p<X[i]) swap(p, X[i]); }
	else {
		for (int i=s; i<min(N, (st+1)*sz); i++) if (p<X[i]) swap(p, X[i]);
		for (int i=st+1; i<et; i++) p=sol(i, p);
		for (int i=et*sz; i<=e; i++) if (p<X[i]) swap(p, X[i]);
	}
	make(st); make(et);
	return p;
}

int main() {
	scanf("%d %d", &N, &Q); M=(N+sz-1)/sz;
	for (int i=0; i<N; i++) scanf("%d", &X[i]);
	for (int i=0; i<M; i++) make(i);
	while (Q--) {
		int s, t, p;
		scanf("%d %d %d", &s, &t, &p); s--; t--;
		if (s>t) printf("%d\n", f(0, t, f(s, N-1, p)));
		else printf("%d\n", f(s, t, p));
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q); M=(N+sz-1)/sz;
  ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:49:31: 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("%d", &X[i]);
                          ~~~~~^~~~~~~~~~~~~
sushi.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &s, &t, &p); s--; t--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 543 ms 504 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 4878 ms 10584 KB Output is correct
2 Correct 4970 ms 10456 KB Output is correct
3 Correct 2623 ms 9980 KB Output is correct
4 Correct 4829 ms 10736 KB Output is correct
5 Correct 3733 ms 10556 KB Output is correct
6 Correct 5393 ms 10748 KB Output is correct
7 Correct 5331 ms 10704 KB Output is correct
8 Correct 5288 ms 10532 KB Output is correct
9 Correct 2146 ms 10280 KB Output is correct
10 Correct 3948 ms 10436 KB Output is correct
11 Correct 2205 ms 10104 KB Output is correct
12 Correct 3876 ms 10288 KB Output is correct
13 Correct 4932 ms 10548 KB Output is correct
14 Correct 4884 ms 10632 KB Output is correct
15 Correct 3092 ms 10160 KB Output is correct
16 Correct 5056 ms 10760 KB Output is correct
17 Correct 3848 ms 10680 KB Output is correct
18 Correct 5488 ms 10428 KB Output is correct
19 Correct 5661 ms 10512 KB Output is correct
20 Correct 5487 ms 10476 KB Output is correct

Subtask #3
0 / 80.0

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