| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 828822 |
2023-08-17T16:47:12 Z |
NK_ |
RMQ (NOI17_rmq) |
C++17 |
|
1 ms |
212 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;
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);
set<int> S = {-1}, G = {-1}; vi A(N), mn(N);
vi C(N);
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]--;
if (C[v] == 0) S.erase(S.find(v));
} else {
if (C[v] == 0) S.insert(v);
C[v]++;
if (C[v] == amt[v]) { G.insert(v); if (have.count(v)) have.erase(v); }
}
}
A[x] = *rbegin(G);
mn[x] = *rbegin(S);
}
C = vi(N, 0); for(auto x : A) if (x != -1) C[x]++;
vi ord(N); iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int x, int y) { return mn[x] > mn[y]; });
for(auto i : ord) {
int x = A[i];
if (x != -1 && C[x] == 1) continue;
auto it = have.lower_bound(mn[i]);
if (it == end(have)) continue;
A[i] = *it; have.erase(it);
if (x != -1) C[x]--;
}
// ST st; st.init(A);
// for(int j = 0; j < Q; j++) {
// auto [l, r, x] = q[j];
// if (st.query(l, r) != x) impossible();
// }
if (sz(have) != 0) impossible();
for(auto x : A) cout << x << " ";
cout << nl;
exit(0-0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 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 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 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 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 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 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
