#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define all(v) v.begin(),v.end()
#define trav(a,v) for(auto&a:v)
#define sz(a) a.size()
typedef long double ld;
using namespace std;
static const long long inf = 1e15;
typedef long long ll;
typedef unsigned long long ull;
struct segtree {
vector<multiset<pair<ll,ll>>> s;
ll n;
segtree(ll n=0) : s(2*n) ,n(n){}
void update(ll pos, ll val, ll nxt) {
ll i = pos;
for (pos += n; pos;) {
auto it = s[pos].find(make_pair(val,i));
if (it != s[pos].end())s[pos].erase(it);
s[pos].insert(make_pair(nxt,i));
pos /= 2;
}
}
pair<ll,ll> query_bigger(ll l, ll r, ll val) {
pair<ll,ll> a = make_pair(inf,inf), b = make_pair(inf,inf);
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l % 2) {
auto it = s[l].lower_bound(make_pair(val, -inf));
if (it != s[l].end()) {
a = min(a, *it);
}
l++;
}
if (r % 2) {
auto it = s[--r].lower_bound(make_pair(val, -inf));
if (it != s[r].end()) {
b = min(b, *it);
}
}
}
return min(a, b);
}
pair<ll, ll> query_smaller(ll l, ll r, ll val) {
pair<ll, ll> a = make_pair(-inf, -inf), b = make_pair(-inf, -inf);
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l % 2) {
auto it = s[l].lower_bound(make_pair(val, -inf));
if (it != s[l].begin()) {
a = max(a, (*--it));
}
l++;
}
if (r % 2) {
auto it = s[--r].lower_bound(make_pair(val, -inf));
if (it != s[r].begin()) {
b = max(b, (*--it));
}
}
}
return max(a, b);
}
};
vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
vector<ll> v;
vector<vector<ll>> g;
vector<ll> howmany(N);
rep(i, 0, X.size()) {
howmany[X[i]]++;
howmany[Y[i]]++;
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
rep(i, 0, N) {
if (howmany[i] == 1) {
v.push_back(i);
break;
}
}
v.push_back(g[v[0]][0]);
rep(i, 1, N) {
if (g[v[i]][0] != v[i - 1]) {
v.push_back(g[v[i]][0]);
}
else v.push_back(g[v[i]][1]);
}
segtree tree(N);
rep(i, 0, N) {
tree.update(i, -1, v[i]);
}
vector<ll> maping(N);
rep(i, 0, v.size())maping[v[i]] = i;
vector<int> ans(E.size());
rep(i, 0, E.size()) {
if (tree.query_smaller(maping[S[i]], maping[E[i]], L[i]).second >= tree.query_bigger(maping[S[i]], maping[E[i]], R[i]).second)ans[i] = 1;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
164 ms |
30956 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
