| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 828818 |
2023-08-17T16:41:51 Z |
NK_ |
RMQ (NOI17_rmq) |
C++17 |
|
1 ms |
456 KB |
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = double;
const int INF = 1e9 + 10;
struct ST {
int level(int x) { return 31 - __builtin_clz(x); }
vi v; V<vi> jmp; int comb(int a, int b) { return min(a, b); }
void init(const vi& _v) {
v = _v; jmp = {v};
for(int j = 1; (1<<j) <= sz(v); j++) {
jmp.pb(vi(sz(v) - (1<<j) + 1));
for(int i = 0; i < sz(jmp[j]); i++) jmp[j][i] = comb(jmp[j-1][i], jmp[j-1][i+(1<<(j-1))]);
}
}
int query(int l, int r) {
int d = level(r-l+1);
return comb(jmp[d][l], jmp[d][r-(1<<d)+1]);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >> Q;
V<vi> E(N+1); V<array<int, 3>> q;
vi amt(N);
for(int i = 0; i < Q; i++) {
int l, r, x; cin >> l >> r >> x;
amt[x]++; q.pb({l, r, x});
E[l].pb(x);
E[r+1].pb(~x);
}
auto impossible = [&]() {
for(int i = 0; i < N; i++) cout << -1 << " ";
cout << nl;
exit(0-0);
};
set<int> have;
for(int i = 0; i < N; i++) have.insert(i);
multiset<int> S = {-1}, G = {-1}; vi A(N), mn(N);
map<int, int> C;
for(int x = 0; x < N; x++) {
for(auto& v : E[x]) {
if (v < 0) {
v = ~v;
if (C[v] == amt[v]) G.erase(v);
C[v]--, S.erase(S.find(v));
} else {
C[v]++, S.insert(v);
if (C[v] == amt[v]) { G.insert(v); if (have.count(v)) have.erase(v); }
}
}
A[x] = *rbegin(G);
mn[x] = *rbegin(S);
}
// for(auto x : A) cout << x << " ";
// cout << nl;
vi CNT(N); for(auto x : A) if (x != -1) CNT[x]++;
for(int i = 0; i < N; i++) {
int x = A[i];
if (x != -1 && CNT[x] == 1) continue;
// cout << i << " " << *rbegin(have) << " " << mn[i] << endl;
auto it = have.lower_bound(mn[i]);
if (it == end(have)) continue;
A[i] = *it; have.erase(it);
if (x != -1) CNT[x]--;
}
ST st; st.init(A);
for(int j = 0; j < Q; j++) {
auto [l, r, x] = q[j];
// cout << st.query(l, r) << " " << x << endl;
if (st.query(l, r) != x) impossible();
}
for(auto x : A) cout << x << " ";
cout << nl;
exit(0-0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Partially correct |
0 ms |
324 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Partially correct |
0 ms |
324 KB |
Output is partially correct |
| 12 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Partially correct |
0 ms |
324 KB |
Output is partially correct |
| 12 |
Incorrect |
1 ms |
456 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
