#include <bits/stdc++.h>
using namespace std;
struct seg {
int L;
int R;
};
const int N = 1e5 + 10, LOG = 18;
int n, q;
seg a[N];
int sparse[N][LOG];
int st[16 * N];
int L[4 * N];
void build(int index, int l, int r) {
if(l > r) return;
if(l == r) {
st[index] = L[l];
return;
}
int mid = (l + r) / 2;
build(2 * index + 1, l, mid);
build(2 * index + 2, mid + 1, r);
st[index] = min(st[2 * index + 1], st[2 * index + 2]);
}
int get(int index, int l, int r, int L, int R) {
if(l > r || r < L || R < l) return 1e9;
if(L <= l && r <= R) return st[index];
int mid = (l + r) / 2;
return min(get(2 * index + 1, l, mid, L, R), get(2 * index + 2, mid + 1, r, L, R));
}
mt19937 rng(time(0));
int random(int l, int r) { return l + (rng() % (r - l + 1)); }
vector<pair<int, int>> Q;
void make_input() {
n = 10, q = 10;
for (int i = 0; i < n; i++) {
int l = random(1, 10);
int r = l + random(1, 4);
a[i].L = l;
a[i].R = r;
}
for (int _i = 0; _i < q; _i++) {
int i = random(1, n);
int j = random(1, n);
do {
i = random(1, n);
j = random(1, n);
} while (i == j);
Q.emplace_back(i, j);
}
}
vector<int> bf_res, my_res;
int dd[N];
vector<int> graf[N];
void run_bf() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j)
if (a[j].L <= a[i].R && a[i].R <= a[j].R)
graf[i].push_back(j);
for (int i = 0; i < q; i++) {
int s = Q[i].first - 1;
int e = Q[i].second - 1;
for (int i = 0; i < n; i++) dd[i] = -1;
vector<int> que(1, s);
dd[s] = 0;
for (int b = 0; b < (int) que.size(); b++) {
int x = que[b];
for (int y : graf[x]) {
if (dd[y] == -1) {
dd[y] = dd[x] + 1;
que.push_back(y);
}
}
}
bf_res.push_back(dd[e]);
}
}
void cmp_res() {
bool OK = true;
for (int i = 0; i < q; i++) {
if (bf_res[i] != my_res[i]) {
OK = false;
}
}
if (OK) {
cout << "AC\n";
} else {
cout << "WA\n";
cout << n << " " << q << '\n';
for (int i = 0; i < n; i++) {
cout << a[i].L << " " << a[i].R << '\n';
}
cout << '\n';
for (int i = 0; i < q; i++) {
cout << Q[i].first << " " << Q[i].second << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// cin >> n >> q;
make_input();
run_bf();
vector<int> compress;
for(int i = 0; i < n; i++) {
// cin >> a[i].L >> a[i].R;
compress.push_back(a[i].L);
compress.push_back(a[i].R);
}
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
for(int i = 0; i < n; i++) {
a[i].L = lower_bound(compress.begin(), compress.end(), a[i].L) - compress.begin();
a[i].R = lower_bound(compress.begin(), compress.end(), a[i].R) - compress.begin();
}
vector<pair<pair<int, bool>, int>> v;
for(int i = 0; i < n; i++) {
v.push_back({{a[i].L, false}, i});
v.push_back({{a[i].R, true}, i});
}
sort(v.begin(), v.end());
int mx = v[0].second;
for(int i = 0; i < v.size(); i++) {
if(v[i].first.second) {
if(a[v[i].second].R == a[mx].R) sparse[v[i].second][0] = -1;
else sparse[v[i].second][0] = mx;
} else {
if(a[mx].R < a[v[i].second].R) mx = v[i].second;
}
}
for (int i = 0; i < n; i++) {
int idx = -1;
for (int j = 0; j < n; j++) if (i != j) {
if (a[j].L <= a[i].R && a[i].R < a[j].R) {
if (idx == -1 || a[idx].R < a[j].R || (a[idx].R == a[j].R && a[idx].L > a[j].L)) {
idx = j;
}
}
}
assert(sparse[i][0] == idx);
}
for(int j = 1; j < LOG; j++) {
for(int i = 0; i < n; i++) {
if(sparse[i][j - 1] == -1) sparse[i][j] = -1;
else sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
}
}
for(int i = 0; i < 4 * N; i++) L[i] = 1e9;
for(int i = 0; i < n; i++) L[a[i].R] = min(L[a[i].R], a[i].L);
build(0, 0, 4 * n);
// vector<int> my_res;
for (auto& P : Q) {
int s = P.first, e = P.second;
s--;
e--;
if(s == e) {
// cout << "0\n";
my_res.push_back(0);
continue;
}
if(a[s].R > a[e].R) {
// cout << "impossible\n";
my_res.push_back(-1);
continue;
}
if(a[s].R >= a[e].L) {
my_res.push_back(1);
// cout << "1\n";
continue;
}
int res = 0;
for(int j = LOG - 1; j >= 0; j--) {
if(sparse[s][j] == -1) continue;
if(a[sparse[s][j]].R >= a[e].L) continue;
s = sparse[s][j];
res += (1 << j);
}
int have = get(0, 0, 4 * n, a[e].L, a[e].R);
if(have <= a[s].R) my_res.push_back(res + 2); //cout << res + 2 << "\n";
else my_res.push_back(-1); //cout << "impossible\n";
}
cmp_res();
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:137:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, bool>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
