oj.uz

Submission #199434

# Submission time Handle Problem Language Result Execution time Memory
199434 2020-02-01T12:26:15 Z dennisstar Sushi (JOI16_sushi) C++17
0 / 100
 12000 ms 24980 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;

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

void make(int t) {
	B[t].clear(); S[t].clear();
	int ub=min((t+1)*500, N);
	for (int i=t*500; i<ub; i++) B[t].eb(X[i], i);
	sort(all(B[t])); for (auto &j:B[t]) S[t].em(j.fi);
}

void upd(int t) {
	auto it=S[t].begin();
	for (auto &i:B[t]) { i.fi=(*it); X[i.se]=i.fi; ++it; }
}

void solve(int t, int &p) {
	S[t].em(p);
	p=(*prev(S[t].end())); S[t].erase(prev(S[t].end()));
}

int main() {
	scanf("%d %d", &N, &Q); M=(N+499)/500;
	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--;
		upd(s/500); upd(t/500);
		if (s<=t&&s/500==t/500) {
			for (int i=s; i<=t; i++) if (X[i]>p) swap(X[i], p);
			make(s/500);
			printf("%d\n", p);
			continue;
		}
		int ub=min((s/500+1)*500, N);
		for (int i=s; i<ub; i++) if (X[i]>p) swap(X[i], p);
		for (int i=s/500+1; i<(s<t?t/500:M); i++) solve(i, p);
		if (s>t) for (int i=0; i<t/500; i++) solve(i, p);
		for (int i=t/500*500; i<=t; i++) if (X[i]>p) swap(X[i], p);
		make(s/500); make(t/500);
		printf("%d\n", p);
	}
	return 0;
}

Compilation message

sushi.cpp: In function 'int main()':
sushi.cpp:32: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+499)/500;
  ~~~~~^~~~~~~~~~~~~~~~~
sushi.cpp:33: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:37: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 261 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12056 ms 24980 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

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