QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235506#6340. Tourism275307894a0 0ms0kbC++142.7kb2023-11-02 20:34:232023-11-02 20:34:23

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 20:34:23]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%