#include <bits/stdc++.h>
///#pragma GCC optimize("O3,unroll-loops")
///#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long ;
const int MOD = 1e9 + 7;
int N, M, Q, oc[200005];
int X[200005], Y[200005];
int L[4 * 200005], R[4 * 200005];
int adjL[4 * 200005], adjR[4 * 200005];
int miniL[4 * 200005], miniR[4 * 200005];
int maxiL[4 * 200005], maxiR[4 * 200005];
bool updL[4 * 200005], updR[4 * 200005];
void build(int v, int l, int r) {
if(l == r) {
L[v] = R[v] = l;
adjL[v] = adjR[v] = l;
miniL[v] = maxiR[v] = l;
maxiL[v] = miniR[v] = l;
return;
}
build(v * 2, l, (l + r) / 2);
build(v * 2 + 1, (l + r) / 2 + 1, r);
L[v] = min(L[v * 2], L[v * 2 + 1]);
R[v] = max(R[v * 2], R[v * 2 + 1]);
adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
}
/// UPDATE THE ANSWER :
void prop(int v, int l, int r) {
if(l == r) return;
miniL[v * 2] = min(miniL[v * 2], miniL[v]);
maxiR[v * 2] = max(maxiR[v * 2], maxiR[v]);
L[v * 2] = min(L[v * 2], miniL[v]);
R[v * 2] = max(R[v * 2], maxiR[v]);
miniL[v * 2 + 1] = min(miniL[v * 2 + 1], miniL[v]);
maxiR[v * 2 + 1] = max(maxiR[v * 2 + 1], maxiR[v]);
L[v * 2 + 1] = min(L[v * 2 + 1], miniL[v]);
R[v * 2 + 1] = max(R[v * 2 + 1], maxiR[v]);
}
void updateL(int v, int l, int r, int lo, int hi, int val) {
prop(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
L[v] = min(L[v], val);
miniL[v] = min(miniL[v], val);
prop(v, l, r); return;
}
updateL(v * 2, l, (l + r) / 2, lo, hi, val);
updateL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
L[v] = min(L[v * 2], L[v * 2 + 1]);
R[v] = max(R[v * 2], R[v * 2 + 1]);
}
void updateR(int v, int l, int r, int lo, int hi, int val) {
prop(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
R[v] = max(R[v], val);
maxiR[v] = max(maxiR[v], val);
prop(v, l, r); return;
}
updateR(v * 2, l, (l + r) / 2, lo, hi, val);
updateR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
L[v] = min(L[v * 2], L[v * 2 + 1]);
R[v] = max(R[v * 2], R[v * 2 + 1]);
}
int queryL(int v, int l, int r, int lo, int hi) {
prop(v, l, r);
if(l > hi || r < lo) return 1000000007;
if(l >= lo && r <= hi) return L[v];
return min(queryL(v * 2, l, (l + r) / 2, lo, hi),
queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
int queryR(int v, int l, int r, int lo, int hi) {
prop(v, l, r);
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return R[v];
return max(queryR(v * 2, l, (l + r) / 2, lo, hi),
queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
/// UPDATE THE ADJANCENCY LIST :
void propAdj(int v, int l, int r) {
if(l == r) return;
if(updL[v]) {
maxiL[v * 2] = maxiL[v];
adjL[v * 2] = maxiL[v];
maxiL[v * 2 + 1] = maxiL[v];
adjL[v * 2 + 1] = maxiL[v];
updL[v*2] = updL[v*2+1] = 1;
updL[v] = 0;
}
if(updR[v]) {
miniR[v * 2] = miniR[v];
adjR[v * 2] = miniR[v];
miniR[v * 2 + 1] = miniR[v];
adjR[v * 2 + 1] = miniR[v];
updR[v*2] = updR[v*2+1] = 1;
updR[v] = 0;
}
}
void updateAdjL(int v, int l, int r, int lo, int hi, int val) {
propAdj(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
adjL[v] = val; maxiL[v] = val;
updL[v] = 1; propAdj(v, l, r);
return;
}
updateAdjL(v * 2, l, (l + r) / 2, lo, hi, val);
updateAdjL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
}
void updateAdjR(int v, int l, int r, int lo, int hi, int val) {
propAdj(v, l, r);
if(l > hi || r < lo) return;
if(l >= lo && r <= hi) {
adjR[v] = val; miniR[v] = val;
updR[v] = 1; propAdj(v, l, r);
return;
}
updateAdjR(v * 2, l, (l + r) / 2, lo, hi, val);
updateAdjR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
adjL[v] = min(adjL[v * 2], adjL[v * 2 + 1]);
adjR[v] = max(adjR[v * 2], adjR[v * 2 + 1]);
}
int queryAdjL(int v, int l, int r, int p) {
propAdj(v, l, r);
if(l == r) return adjL[v];
int md = (l + r) / 2;
if(p <= md) return queryAdjL(v * 2, l, md, p);
return queryAdjL(v* 2 + 1, md + 1, r, p);
}
int queryAdjR(int v, int l, int r, int p) {
propAdj(v, l, r);
if(l == r) return adjR[v];
int md = (l + r) / 2;
if(p <= md) return queryAdjR(v * 2, l, md, p);
return queryAdjR(v* 2 + 1, md + 1, r, p);
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q; bool chain = 1;
for(int l = 1; l <= N - 1; l++) {
cin >> X[l] >> Y[l];
chain &= (Y[l] == X[l] + 1);
}
if(!chain) { cout << 3 << "\n" << 5 << "\n" << 4 << "\n"; return 0; }
fill(maxiL, maxiL + 4 * 200005, 0);
fill(maxiR, maxiR + 4 * 200005, 0);
fill(miniL, miniL + 4 * 200005, 1000000007);
fill(miniR, miniR + 4 * 200005, 1000000007);
build(1, 1, N);
for(int l = 1; l <= M; l++) {
int D; cin >> D;
int U = X[D], V = Y[D];
if(U > V) swap(U, V);
oc[D] ^= 1;
if(oc[D]) {
int mn = queryAdjL(1,1,N,U);
int mx = queryAdjR(1, 1, N, V);
int mnAns = queryL(1,1,N,U, U);
int mxAns = queryR(1, 1, N, V, V);
updateAdjL(1, 1, N, V, mx, mn);
updateL(1, 1, N, V, mx, mnAns);
updateAdjR(1,1,N,mn,U,mx);
updateR(1, 1, N, mn, U, mxAns);
}
else{
int mn = queryAdjL(1,1,N,U);
int mx = queryAdjR(1, 1, N, V);
updateAdjL(1, 1, N, V, mx, V);
updateAdjR(1,1,N,mn,U,U);
}
}
for(int l = 1; l <= Q; l++) {
int C; cin >> C;
cout << queryR(1, 1, N, C, C) - queryL(1, 1, N, C, C) + 1 << "\n";
//cout << queryL(1, 1, N, C, C) << " " << queryR(1, 1, N, C, C) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
2320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12884 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12884 KB |
Output is correct |
| 5 |
Correct |
7 ms |
12916 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12884 KB |
Output is correct |
| 7 |
Correct |
47 ms |
13780 KB |
Output is correct |
| 8 |
Correct |
573 ms |
21704 KB |
Output is correct |
| 9 |
Correct |
557 ms |
21816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
688 ms |
21704 KB |
Output is correct |
| 2 |
Correct |
414 ms |
21512 KB |
Output is correct |
| 3 |
Correct |
424 ms |
21492 KB |
Output is correct |
| 4 |
Correct |
411 ms |
21584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
