oj.uz

Submission #199462

# Submission time Handle Problem Language Result Execution time Memory
199462 2020-02-01T13:10:43 Z dennisstar Sushi (JOI16_sushi) C++17
15 / 100
 5592 ms 7492 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[810]; priority_queue<int> S[810];

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 536 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 4900 ms 7288 KB Output is correct
2 Correct 4818 ms 7008 KB Output is correct
3 Correct 2757 ms 7136 KB Output is correct
4 Correct 4842 ms 7288 KB Output is correct
5 Correct 3633 ms 7416 KB Output is correct
6 Correct 5395 ms 7164 KB Output is correct
7 Correct 5417 ms 7312 KB Output is correct
8 Correct 5433 ms 7492 KB Output is correct
9 Correct 2037 ms 7160 KB Output is correct
10 Correct 3711 ms 7288 KB Output is correct
11 Correct 2085 ms 7164 KB Output is correct
12 Correct 3785 ms 7160 KB Output is correct
13 Correct 4874 ms 7352 KB Output is correct
14 Correct 4923 ms 7288 KB Output is correct
15 Correct 2923 ms 7212 KB Output is correct
16 Correct 4952 ms 7000 KB Output is correct
17 Correct 3653 ms 7032 KB Output is correct
18 Correct 5592 ms 7384 KB Output is correct
19 Correct 5463 ms 7132 KB Output is correct
20 Correct 5448 ms 7068 KB Output is correct

Subtask #3
0 / 80.0

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