oj.uz

Submission #199466

# Submission time Handle Problem Language Result Execution time Memory
199466 2020-02-01T13:16:22 Z dennisstar Sushi (JOI16_sushi) C++17
15 / 100
 5786 ms 7644 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 = 500;
 
int N, M, Q, X[400010];
vector<pii> B[1610]; priority_queue<int> S[1610];
 
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 547 ms 508 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 5264 ms 7340 KB Output is correct
2 Correct 5786 ms 7032 KB Output is correct
3 Correct 3520 ms 6904 KB Output is correct
4 Correct 5712 ms 7092 KB Output is correct
5 Correct 3706 ms 7252 KB Output is correct
6 Correct 5532 ms 7432 KB Output is correct
7 Correct 5521 ms 7460 KB Output is correct
8 Correct 5394 ms 7552 KB Output is correct
9 Correct 2086 ms 7188 KB Output is correct
10 Correct 3702 ms 7292 KB Output is correct
11 Correct 2071 ms 7308 KB Output is correct
12 Correct 3750 ms 7364 KB Output is correct
13 Correct 4919 ms 7608 KB Output is correct
14 Correct 4869 ms 7260 KB Output is correct
15 Correct 2861 ms 7300 KB Output is correct
16 Correct 4970 ms 7448 KB Output is correct
17 Correct 3607 ms 7316 KB Output is correct
18 Correct 5518 ms 7644 KB Output is correct
19 Correct 5525 ms 7416 KB Output is correct
20 Correct 5495 ms 7396 KB Output is correct

Subtask #3
0 / 80.0

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