| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789182 |
2023-07-21T07:08:58 Z |
반딧불(#10041) |
Tourism (JOI23_tourism) |
C++17 |
|
2 ms |
2644 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 300;
int n, k, q;
vector<int> link[100002];
int inCnt, in[100002], out[100002], idx[100002];
int eventCnt, eventIn[100002], eventOut[100002], event[200002];
int par[100002], LCADB[100002][20], depth[100002];
int arr[100002];
int spsR[200002][18];
void dfs(int x, int p=-1){
in[x] = ++inCnt;
idx[in[x]] = x;
eventIn[x] = eventOut[x] = ++eventCnt;
event[eventIn[x]] = depth[x];
for(auto y: link[x]){
if(y==p) continue;
par[y] = x, depth[y] = depth[x] + 1;
dfs(y, x);
eventOut[x] = ++eventCnt;
event[eventOut[x]] = depth[x];
}
out[x] = inCnt;
}
int p[200002];
inline int getDist(int x, int y){
if(x==y) return 0;
if(in[x]>in[y]) swap(x,y);
int td=depth[x]+depth[y];
x=eventOut[x], y=eventIn[y];
if(x>y) swap(x, y);
int d=p[y-x+1];
return td - 2 * min(spsR[x][d], spsR[y-(1<<d)+1][d]);
}
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
bool operator<(const Query &nxt)const{
if(l/B != nxt.l/B) return l/B < nxt.l/B;
return r < nxt.r;
}
} query[100002];
struct segTree{
int tree[1<<18];
inline void add(int i, int l, int r, int x, int v){
tree[i] += v;
if(l==r) return;
int m = (l+r)>>1;
if(x<=m) add(i*2, l, m, x, v);
else add(i*2+1, m+1, r, x, v);
}
inline int nxt(int i, int l, int r, int x){
if(r<x||!tree[i]) return r+1;
if(l==r) return l;
int m = (l+r)>>1;
int v = nxt(i*2,l,m,x);
return v==m+1 ? nxt(i*2+1, m+1, r, x) : v;
}
inline int prv(int i, int l, int r, int x){
if(x<l||!tree[i]) return l-1;
if(l==r) return l;
int m = (l+r)>>1;
int v = prv(i*2+1, m+1, r, x);
return v==m ? prv(i*2, l, m, x) : v;
}
} tree;
int ans[100002];
int distSum, cnt;
inline void add(int x){
if(cnt==0) cnt++, tree.add(1, 1, n, arr[x], 1);
else if(cnt==1){
cnt++;
int tmp = arr[x]==1 ? 0 : tree.prv(1, 1, n, arr[x]);
if(tmp==0) tmp = tree.nxt(1, 1, n, arr[x]);
distSum += getDist(idx[arr[x]], idx[tmp]) * 2;
tree.add(1, 1, n, arr[x], 1);
}
else{
cnt++;
int prv = arr[x]==1 ? 0 : tree.prv(1, 1, n, arr[x]);
if(prv==0) prv = tree.prv(1, 1, n, n);
int nxt = arr[x]==n ? n+1 : tree.nxt(1, 1, n, arr[x]);
if(nxt==n+1) nxt = tree.nxt(1, 1, n, 1);
distSum += getDist(idx[arr[x]], idx[prv]) + getDist(idx[arr[x]], idx[nxt]) - getDist(idx[prv], idx[nxt]);
tree.add(1, 1, n, arr[x], 1);
}
}
inline void del(int x){
if(cnt<=1) cnt--, tree.add(1, 1, n, arr[x], -1), distSum = 0;
else{
cnt--;
tree.add(1, 1, n, arr[x], -1);
int prv = arr[x]==1 ? 0 : tree.prv(1, 1, n, arr[x]);
if(prv==0) prv = tree.prv(1, 1, n, n);
int nxt = arr[x]==n ? n+1 : tree.nxt(1, 1, n, arr[x]);
if(nxt==n+1) nxt = tree.nxt(1, 1, n, 1);
distSum -= getDist(idx[arr[x]], idx[prv]) + getDist(idx[arr[x]], idx[nxt]) - getDist(idx[prv], idx[nxt]);
}
}
int main(){
scanf("%d %d %d", &n, &k, &q);
for(int i=1; i<n; i++){
int x, y;
// scanf("%d %d", &x, &y);
x=i, y=i+1;
link[x].push_back(y);
link[y].push_back(x);
}
dfs(1);
for(int i=1; i<=n+n; i++) spsR[i][0] = event[i];
for(int d=1; d<18; d++) for(int i=1; i<=n+n; i++)
spsR[i][d] = min(spsR[i][d-1], (i+(1<<(d-1))) > n+n ? INT_MAX : spsR[i+(1<<(d-1))][d-1]);
for(int i=1; i<=n+n+1; i++){
int j=0;
while((1<<(j+1))<=i) j++;
p[i]=j;
}
for(int i=1; i<=k; i++){
scanf("%d", &arr[i]);
arr[i] = in[arr[i]];
}
for(int i=1; i<=q; i++){
scanf("%d %d", &query[i].l, &query[i].r);
query[i].idx = i;
}
sort(query+1, query+q+1);
int l = 1, r = 0;
for(int i=1; i<=q; i++){
while(r < query[i].r) add(++r);
while(l > query[i].l) add(--l);
while(r > query[i].r) del(r--);
while(l < query[i].l) del(l++);
ans[query[i].idx] = distSum / 2 + 1;
}
for(int i=1; i<=q; i++){
printf("%d\n", ans[i]);
}
}
Compilation message
tourism.cpp: In function 'int main()':
tourism.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
tourism.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d %d", &query[i].l, &query[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
