#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "werewolf.h"
#else
#endif
struct ovo {
ovo *l, *r;
int m;
ovo() {
l = r = NULL;
m = -1;
}
void P() {
if(l == NULL) l = new ovo();
if(r == NULL) r = new ovo();
m = max(l->m, r->m);
}
};
int si, vl;
void _G(int l, int r, ovo *&t) {
if(t == NULL) t = new ovo();
if(l == r) {
t->m = vl;
return;
}
int m = (l + r) / 2;
if(m >= si) _G(l, m, t->l);
else _G(m + 1, r, t->r);
t->P();
}
int sl, sr;
int _S(int l, int r, ovo *&t) {
if(l > sr || r < sl || t == NULL) return -1;
if(l >= sl && r <= sr) return t->m;
int m = (l + r) / 2;
return max(_S(l, m, t->l), _S(m + 1, r, t->r));
}
struct doo {
const int n;
ovo *rt;
doo(int _n) : n(_n), rt(NULL) {}
void set(int _si, int _vl) {
_G(1, n, rt);
si = _si; vl = _vl;
}
int max(int _sl, int _sr) {
sl = _sl; sr = _sr;
return _S(1, n, rt);
return 0;
}
};
const int N = 200005, L = 20;
vint v[N], xs[2][N];
int ups[2][N], up[2][N][L], rm, io[2][N][2];
int P(int x) {
return (ups[rm][x] == -1 ? x : ups[rm][x] = P(ups[rm][x]));
}
void U(int x, int y) {
if((rm && y < x) || (!rm && y > x) || P(x) == P(y)) return;
up[rm][P(y)][0] = P(x);
xs[rm][P(x)].push_back(P(y));
ups[rm][P(y)] = P(x);
}
void sgs(int x) {
for(int i = 1; i < L; ++i) {
if(up[rm][x][i - 1] == -1) break;
up[rm][x][i] = up[rm][up[rm][x][i - 1]][i - 1];
}
io[rm][x][1] = io[rm][x][0];
for(int i = 0; i < sz(xs[rm][x]); ++i) {
io[rm][xs[rm][x][i]][0] = io[rm][x][1] + 1;
sgs(xs[rm][x][i]);
io[rm][x][1] = io[rm][xs[rm][x][i]][1];
}
}
int W(int x, int y, int z) {
for(int i = L - 1; i >= 0; --i) {
if(up[z][x][i] == -1) continue;
if((z && up[z][x][i] >= y) || (!z && up[z][x][i] <= y)) {
x = up[z][x][i];
}
}
return x;
}
vint check_validity(int n, vint x, vint y, vint s, vint e, vint l, vint r) {
// // // // // // // //
int m = sz(x);
int q = sz(s);
vint dr(q);
// // // // // // // //
for(int i = 0; i < m; ++i) {
v[x[i]].push_back(y[i]);
v[y[i]].push_back(x[i]);
}
// // // // // // // //
for(int i = 0; i < n; ++i) {
ups[0][i] = ups[1][i] = -1;
for(int j = 0; j < L; ++j) {
up[0][i][j] = up[1][i][j] = -1;
}
}
// // // // // // // //
rm = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < sz(v[i]); ++j) {
U(i, v[i][j]);
}
}
rm = 1;
for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < sz(v[i]); ++j) {
U(i, v[i][j]);
}
}
// // // // // // // //
for(rm = 0; rm < 2; ++rm) {
int bg = -1;
for(int i = 0; i < n; ++i) {
if(up[rm][i][0] == -1) {
io[rm][i][0] = (bg == -1 ? 1 : io[rm][bg][1] + 1);
sgs(i);
bg = i;
}
}
}
// // // // // // // //
#ifdef wambulex
int rml = 1;
cout << "|-[ up ]-|" << endl;
for(int i = 0; i < n; ++i) {
cout << up[rml][i][0] << " ";
}
cout << endl << "________" << endl;
cout << "|-[ in ]-|" << endl;
for(int i = 0; i < n; ++i) {
cout << io[rml][i][0] << " ";
}
cout << endl << "________" << endl;
cout << "|-[ out ]-|" << endl;
for(int i = 0; i < n; ++i) {
cout << io[rml][i][1] << " ";
}
cout << endl << "________" << endl;
#endif
// // // // // // // //
vector<pair<pair<int, int>, pair<int, int>>> ve[n + 1];
for(int i = 0; i < q; ++i) {
int x = W(s[i], l[i], 1);
int y = W(e[i], r[i], 0);
int l0 = io[0][y][0];
int r0 = io[0][y][1];
int l1 = io[1][x][0];
int r1 = io[1][x][1];
ve[r0].push_back({{l1, r1}, {l0, i}});
}
// // // // // // // //
int a[n + 1];
for(int i = 0; i < n; ++i) {
a[io[0][i][0]] = i;
}
// // // // // // // //
doo st(n);
for(int i = 1; i <= n; ++i) {
st.set(io[1][a[i]][0], i);
for(int j = 0; j < ve[i].size(); ++j) {
if(st.max(ve[i][j].first.first, ve[i][j].first.second) >= ve[i][j].second.first) {
dr[ve[i][j].second.second] = 1;
}
}
}
// // // // // // // //
#ifdef wambule
#endif
// // // // // // // //
return dr;
// // // // // // // //
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int ty = 3;
if(ty == 0) {
int n;
cin >> n;
doo st(n);
while(7) {
int x, y, z;
cin >> x >> y >> z;
if(x) st.set(y, z);
else cout << st.max(y, z) << endl;
}
} else if(ty == 1) {
// // // // // // // //
string s;
char c;
while(8) {
cin >> c;
if(c == '.') break;
if(c == '[') c = '{';
if(c == ']') c = '}';
s += c;
if(c == ',') s += ' ';
}
cout << endl << s << endl;
// // // // // // // //
} else {
// // // // // // // //
vint v;
v = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
for(int i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
cout << endl;
// // // // // // // //
}
return 0;
}
#endif
Compilation message
werewolf.cpp: In function 'vint check_validity(int, vint, vint, vint, vint, vint, vint)':
werewolf.cpp:180:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int j = 0; j < ve[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
836 ms |
98028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14444 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
14444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
