oj.uz

Submission #199469

# Submission time Handle Problem Language Result Execution time Memory
199469 2020-02-01T13:32:25 Z dennisstar Sushi (JOI16_sushi) C++17
15 / 100
 6077 ms 7592 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[(400000/sz)+10]; priority_queue<int> S[(400000/sz)+10];

inline void make(int t) {
	B[t].clear(); while(!S[t].empty()) S[t].pop();
	for (int i=t*sz; i<(t+1)*sz; 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<(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:47: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:48: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:52: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 526 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 4866 ms 7452 KB Output is correct
2 Correct 4756 ms 7204 KB Output is correct
3 Correct 2795 ms 6860 KB Output is correct
4 Correct 4826 ms 7364 KB Output is correct
5 Correct 3472 ms 7416 KB Output is correct
6 Correct 6077 ms 7288 KB Output is correct
7 Correct 5979 ms 7516 KB Output is correct
8 Correct 5936 ms 7428 KB Output is correct
9 Correct 2644 ms 7176 KB Output is correct
10 Correct 3547 ms 7160 KB Output is correct
11 Correct 2710 ms 7032 KB Output is correct
12 Correct 4168 ms 7416 KB Output is correct
13 Correct 4711 ms 7416 KB Output is correct
14 Correct 4802 ms 7452 KB Output is correct
15 Correct 2831 ms 7072 KB Output is correct
16 Correct 4772 ms 7144 KB Output is correct
17 Correct 4082 ms 7324 KB Output is correct
18 Correct 6059 ms 7132 KB Output is correct
19 Correct 5960 ms 7592 KB Output is correct
20 Correct 5243 ms 7416 KB Output is correct

Subtask #3
0 / 80.0

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