QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461531 | #6340. Tourism | Rafi22# | 7 | 93ms | 20716kb | C++20 | 2.7kb | 2024-07-02 19:58:09 | 2024-07-02 19:58:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
#define endl '\n'
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=998244353;
const int N=100007,S=300,pot=1<<17;
int seg[2*pot+7];
int seg1[2*pot+7];
int que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg[v];
if(r<a||l>b) return inf;
return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
int que1(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg1[v];
if(r<a||l>b) return -inf;
return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}
vector<pair<int,int>>W[N];
struct Z
{
int l,r,i;
};
bool cmp(Z a,Z b)
{
if(a.l/S==b.l/S) return a.r<b.r;
else return a.l<b.l;
}
vector<int>G[N];
int O[N];
int ile[N];
int c[N];
int res[N];
int pre[N],post[N],cc;
void dfs(int v,int o)
{
pre[v]=++cc;
O[v]=o;
for(auto u:G[v])
{
if(u==o) continue;
dfs(u,v);
}
post[v]=cc;
}
int ans;
void add(int v)
{
while(v!=0)
{
ile[v]++;
if(ile[v]==1) ans++;
v=O[v];
}
}
void del(int v)
{
while(v!=0)
{
ile[v]--;
if(ile[v]==0) ans--;
v=O[v];
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
FOR(i,1,n-1)
{
int a,b;
cin>>a>>b;
G[a].pb(b);
G[b].pb(a);
}
dfs(1,0);
for(int i=1;i<=2*pot;i++)
{
seg[i]=inf;
seg1[i]=-inf;
}
for(int i=1;i<=m;i++)
{
cin>>c[i];
seg[i+pot-1]=pre[c[i]];
seg1[i+pot-1]=pre[c[i]];
}
for(int i=pot-1;i>0;i--)
{
seg[i]=min(seg[2*i],seg[2*i+1]);
seg1[i]=max(seg1[2*i],seg1[2*i+1]);
}
vector<Z>Q;
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
Q.pb({l,r,i});
int L=que(1,l,r,1,pot),R=que1(1,l,r,1,pot);
cout<<R-L+1<<endl;
//W[L].pb({R,i});
}
/*sort(all(Q),cmp);
int L=0,R=0;
for(auto x:Q)
{
while(L<x.l)
{
del(c[L]);
L++;
}
while(L>x.l)
{
L--;
add(c[L]);
}
while(R>x.r)
{
del(c[R]);
R--;
}
while(R<x.r)
{
R++;
add(c[R]);
}
res[x.i]=ans;
}
for(int i=1;i<=n;i++)
{
}
for(int i=1;i<=q;i++) cout<<res[i]<<endl;*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7224kb
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:
160 165 164 163 163 165 165 149 165 165 163 165 164 163 90 163 161 163 165 156 165 165 160 154 111 125 160 164 159 165 163 165 160 153 160 165 165 163 163 163 165 163 160 165 160 165 165 160 160 153 163 164 153 131 164 165 137 163 165 124 160 165 163 165 89 163 164 165 154 165 165 165 165 121 163 16...
result:
wrong answer 1st numbers differ - expected: '67', found: '160'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 7
Accepted
Test #56:
score: 7
Accepted
time: 63ms
memory: 15216kb
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:
55319 55319 55313 55306 55319 53676 55320 55301 55319 55319 55268 55319 55318 55320 55311 55311 55319 55275 55301 55319 55319 55317 55320 55319 55319 55318 55295 55318 55319 55319 55319 55248 55319 55320 55319 55319 55319 55319 55319 55319 55320 55301 55319 55186 55204 55320 55319 55319 55297 55318 ...
result:
ok 75523 numbers
Test #57:
score: 0
Accepted
time: 43ms
memory: 17432kb
input:
80807 56552 65576 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:
80782 80805 80805 80769 80805 80805 80805 80791 80805 80782 80805 80805 80783 80805 80802 80805 80334 80791 80777 80805 80805 80802 80805 80805 80805 80805 80805 80758 80805 80789 80805 80790 80805 80805 80805 80805 80781 80777 80805 80805 80805 80805 80802 80805 80805 80805 80805 80777 80777 80805 ...
result:
ok 65576 numbers
Test #58:
score: 0
Accepted
time: 47ms
memory: 18668kb
input:
91904 82063 54619 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:
91904 91883 91878 91896 91897 91902 91902 91901 91748 91902 91904 91904 91901 91904 91896 91904 91896 91901 91901 91904 91900 91886 91902 91904 91894 91902 91853 91885 91893 91893 91902 91900 91902 91886 91902 91904 91416 91904 91901 91904 91904 91902 91904 91904 91902 91904 91828 91809 91904 91875 ...
result:
ok 54619 numbers
Test #59:
score: 0
Accepted
time: 92ms
memory: 20216kb
input:
100000 100000 100000 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...
output:
99999 99954 99991 99993 99986 99942 99993 99986 99994 99993 99993 99993 99989 99986 99999 99991 99994 99956 99999 99989 99991 99999 99991 99981 99973 99993 99999 99983 99986 99991 99986 99999 99988 99954 99983 99999 99983 99993 99999 99993 99986 99991 99999 99999 99999 99991 99993 99993 99837 99990 ...
result:
ok 100000 numbers
Test #60:
score: 0
Accepted
time: 83ms
memory: 20264kb
input:
100000 100000 100000 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...
output:
100000 99997 99998 99992 99992 99970 99996 99981 99981 99997 99982 99981 99990 99973 99963 99997 99997 99537 99997 99990 99997 99997 99990 100000 99997 99987 99943 100000 99981 99981 99996 99960 99998 99997 100000 99991 99754 99961 99960 99990 99990 100000 99997 99963 99981 99935 99991 100000 99997 ...
result:
ok 100000 numbers
Test #61:
score: 0
Accepted
time: 86ms
memory: 19860kb
input:
100000 100000 100000 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...
output:
99996 99998 99998 99998 99994 99915 99996 99972 99996 99998 99998 99837 99996 99998 99996 99994 99989 99942 99998 99603 99998 99972 99981 99915 99463 99994 99994 99994 99996 99969 99972 99989 99998 99989 99998 99603 99843 99959 99998 99998 99998 99996 99998 99998 99996 99998 99996 99998 99994 99998 ...
result:
ok 100000 numbers
Test #62:
score: 0
Accepted
time: 93ms
memory: 20716kb
input:
100000 100000 100000 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...
output:
99997 99994 99951 99998 99994 99998 99990 100000 100000 100000 99996 100000 99994 99980 99998 99990 99967 99994 100000 100000 99998 99997 99994 99991 100000 100000 100000 99970 100000 99997 99998 100000 99998 99994 99997 99981 99994 99982 99997 100000 100000 99997 99998 99997 100000 100000 99997 100...
result:
ok 100000 numbers
Test #63:
score: 0
Accepted
time: 89ms
memory: 18908kb
input:
100000 100000 100000 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...
output:
99995 99990 99997 99999 99999 99999 99999 99999 99997 99971 99969 99999 99999 99997 99999 99999 99999 99990 99999 99999 99990 99999 99997 99999 99999 99999 99999 99999 99999 99894 99999 99913 99999 99999 99973 99999 99986 99999 99999 99999 99997 99999 99990 99989 99990 99999 99999 99999 99997 99990 ...
result:
ok 100000 numbers
Test #64:
score: 0
Accepted
time: 78ms
memory: 19776kb
input:
100000 100000 100000 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...
output:
99720 99788 99790 99720 99916 99714 99738 99834 99815 99707 99944 99584 99856 99930 99916 99856 99982 99796 99627 99754 99782 99790 99788 99848 99627 99982 99834 99834 99751 99944 99728 99751 99817 99944 99796 99720 99831 99916 99831 99728 99707 99627 99859 99668 99848 99771 99710 99710 99728 99838 ...
result:
ok 100000 numbers
Test #65:
score: 0
Accepted
time: 80ms
memory: 19776kb
input:
100000 100000 100000 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...
output:
99649 99852 99852 99852 99632 99758 99761 99820 99730 99750 99887 99783 99721 99865 99802 99867 99798 99811 99553 99691 99852 99750 99787 99774 99948 99774 99695 99811 99649 99811 99908 99975 99806 99761 99760 99820 99862 99806 99903 99798 99783 99691 99811 99903 99908 99865 99811 99632 99750 99948 ...
result:
ok 100000 numbers
Test #66:
score: 0
Accepted
time: 71ms
memory: 20496kb
input:
100000 100000 100000 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...
output:
99753 99961 99806 99756 99720 99900 99749 99823 99720 99846 99756 99602 99950 99749 99841 99818 99558 99792 99762 99900 99719 99750 99756 99856 99756 99950 99728 99934 99884 99660 99706 99762 99884 99977 99793 99860 99756 99602 99770 99833 99764 99841 99558 99937 99756 99950 99950 99756 99910 99729 ...
result:
ok 100000 numbers
Test #67:
score: 0
Accepted
time: 42ms
memory: 20116kb
input:
100000 1 100000 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 5...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Test #68:
score: 0
Accepted
time: 64ms
memory: 19004kb
input:
100000 100000 100000 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...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 numbers
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 10ms
memory: 10808kb
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:
53547 52464 47444 48219 52115 51607 50507 50757 45996 51680 48315 52427 49252 50917 49910 54047 44117 50193 52500 52171 52410 52517 52072 53601 53750 47940 49907 50195 53693 53403 48444 42297 50311 50726 54008 52172 53202 48951 51928 51683 52725 52842 45986 52387 51049 49844 53454 52365 52972 52561 ...
result:
wrong answer 1st numbers differ - expected: '276', found: '53547'
Subtask #5:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 77ms
memory: 12944kb
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:
55965 55897 55964 55965 55965 55965 55874 55964 55944 55945 55965 55965 55965 55965 55965 55962 55965 55965 55965 55965 55964 55962 55961 55964 55965 55962 55964 55963 55958 55965 55965 55958 55965 55952 55940 55965 55965 55965 55965 55964 55965 55964 55964 55964 55958 55956 55964 55965 55964 55965 ...
result:
wrong answer 1st numbers differ - expected: '42788', found: '55965'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%