QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235506 | #6340. Tourism | 275307894a | 0 | 0ms | 0kb | C++14 | 2.7kb | 2023-11-02 20:34:23 | 2023-11-02 20:34:23 |
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e2+5,M=5e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,q,A[N];
vector<int> S[N];
int fa[N],d[N],Id[N],Ih,Tp[N],siz[N],son[N];
void dfs1(int x,int La){
fa[x]=La;d[x]=d[La]+1;siz[x]=1;
for(int i:S[x]) if(i^La) dfs1(i,x),siz[x]+=siz[i],siz[i]>siz[son[x]]&&(son[x]=i);
}
void dfs2(int x,int La){
Tp[x]=La;Id[x]=++Ih;if(son[x]) dfs2(son[x],La);
for(int i:S[x]) if(i^fa[x]&&i^son[x]) dfs2(i,i);
}
int LCA(int x,int y){
while(Tp[x]^Tp[y]) d[Tp[x]]>d[Tp[y]]?(x=fa[Tp[x]]):(y=fa[Tp[y]]);
return d[x]<d[y]?x:y;
}
int mx[N][20],mi[N][20];
int MAX(int x,int y){return Id[x]>Id[y]?x:y;}
int MIN(int x,int y){return Id[x]<Id[y]?x:y;}
int qx(int x,int y){int d=__lg(y-x+1);return MAX(mx[x][d],mx[y-(1<<d)+1][d]);}
int qi(int x,int y){int d=__lg(y-x+1);return MIN(mi[x][d],mi[y-(1<<d)+1][d]);}
struct seg{int l,r,col;};vector<seg> P[N];
vector<pii> Q[N];
int ans[N];
namespace BIT{
int f[N];void add(int x,int y){while(x) f[x]+=y,assert(f[x]>=0),x-=x&-x;}
int qry(int x){int ans=0;while(x<=m) ans+=f[x],x+=x&-x;return ans;}
}
void Add(int x,int c){
while(x){
int y=Tp[x],r=d[x];
while(!P[y].empty()){
seg p=P[y].back();
if(r<p.l) break;
P[y].pop_back();
BIT::add(p.col,-(min(r,p.r)-p.l+1));
if(r>=p.r) continue;
p.l=r+1;P[y].emplace_back(p);
}
BIT::add(c,r-d[y]+1);P[y].push_back((seg){d[y],r,c});
x=fa[y];
}
}
void Solve(){
int i,j;scanf("%d%d%d",&n,&m,&q);
for(i=1;i<n;i++) {
int x,y;scanf("%d%d",&x,&y);
S[x].emplace_back(y);S[y].emplace_back(x);
}
dfs1(1,0);dfs2(1,1);
for(i=1;i<=m;i++) scanf("%d",&A[i]);
for(i=m;i;i--) {
for(mx[i][0]=A[i],j=1;i+(1<<j)-1<=m;j++) mx[i][j]=MAX(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
for(mi[i][0]=A[i],j=1;i+(1<<j)-1<=m;j++) mi[i][j]=MIN(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
}
for(i=1;i<=q;i++) {
int x,y;scanf("%d%d",&x,&y);
Q[y].emplace_back(x,i);
ans[i]=-d[LCA(qx(x,y),qi(x,y))]+1;
}
for(i=1;i<=m;i++){
Add(A[i],i);
for(auto j:Q[i]) ans[j.se]+=BIT::qry(j.fi);
}
for(i=1;i<=q;i++) printf("%d\n",ans[i]);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
166 249 224 158 52 52 82 158 36 117 158 119 117 5 82 158 18 22 36 82 143 105 36 22 152 36 92 117 2 123 158 5 134 119 89 31 119 92 48 105 149 149 17 108 31 134 50 3 52 63 158 3 51 42 22 17 10 103 158 50 122 92 85 50 78 117 159 36 20 143 115 158 83 20 4 142 22 23 3 96 10 19 134 8 10 151 92 65 108 89 5...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #56:
score: 0
Runtime Error
input:
55321 88650 75523 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #69:
score: 0
Runtime Error
input:
54738 54525 1797 45211 4527 4527 43609 4527 19876 16325 43609 32183 4527 16325 32579 43609 25554 32183 38972 45211 53953 16325 19810 10881 19810 45211 12698 27967 19810 25554 46338 51894 45211 25388 16325 512 25554 43609 7820 10206 512 30021 32183 48647 43609 46338 44138 16766 7820 10023 53953 19810...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #102:
score: 0
Runtime Error
input:
55965 89652 95687 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%