oj.uz

Submission #199453

# Submission time Handle Problem Language Result Execution time Memory
199453 2020-02-01T12:53:37 Z dennisstar Sushi (JOI16_sushi) C++17
15 / 100
 5339 ms 12016 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]), [](pii p1, pii p2){ return p1.fi>p2.fi; });
	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 solve(int t, int p) {
	S[t].em(p); p=S[t].top(); S[t].pop();
	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--;
		int sb=s/sz, tb=t/sz;
		upd(sb); upd(tb);
		if (s<=t&&sb==tb) {
			for (int i=s; i<=t; i++) if (X[i]>p) swap(X[i], p);
			make(sb);
			printf("%d\n", p);
			continue;
		}
		int ub=min((sb+1)*sz, N);
		for (int i=s; i<ub; i++) if (X[i]>p) swap(X[i], p);
		ub=s<t?tb:M;
		for (int i=sb+1; i<tb; i++) p=solve(i, p);
		if (s>t) for (int i=0; i<tb; i++) p=solve(i, p);
		for (int i=tb*sz; i<=t; i++) if (X[i]>p) swap(X[i], p);
		make(sb); make(tb);
		printf("%d\n", p);
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:35: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:36: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:40: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 315 ms 480 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 5025 ms 7176 KB Output is correct
2 Correct 4880 ms 10328 KB Output is correct
3 Correct 2395 ms 8064 KB Output is correct
4 Correct 4764 ms 11920 KB Output is correct
5 Correct 3530 ms 11648 KB Output is correct
6 Correct 5253 ms 11684 KB Output is correct
7 Correct 5244 ms 11896 KB Output is correct
8 Correct 5239 ms 12016 KB Output is correct
9 Correct 1876 ms 8056 KB Output is correct
10 Correct 3628 ms 10440 KB Output is correct
11 Correct 1840 ms 8028 KB Output is correct
12 Correct 3691 ms 10276 KB Output is correct
13 Correct 4738 ms 11660 KB Output is correct
14 Correct 4804 ms 10152 KB Output is correct
15 Correct 2413 ms 8108 KB Output is correct
16 Correct 4812 ms 11524 KB Output is correct
17 Correct 3533 ms 11640 KB Output is correct
18 Correct 5275 ms 11820 KB Output is correct
19 Correct 5263 ms 11516 KB Output is correct
20 Correct 5339 ms 11840 KB Output is correct

Subtask #3
0 / 80.0

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