QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#644897 | #7626. Quake and Rebuild | Displace_ | TL | 1655ms | 8044kb | C++14 | 3.2kb | 2024-10-16 15:53:35 | 2024-10-16 15:53:35 |
Judging History
answer
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
#define ep emplace_back
template <typename T>inline void read(T &x){
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const int N=2e5+5;
const int B=450;
int n, m;
int lp[B], rp[B], bid[N];
int fa[N], nxt[N], dis[N];
int ins[N];
int dt[B];
inline void rebuild(int i){
if(dt[i]>=B) return ;
for(int j=lp[i]; j<=rp[i]; ++j){
int x=j; dis[j]=0;
while(x>=lp[i]) ++dis[j], x=max(1, fa[x]-dt[i]);
nxt[j]=x;
}
}
#define gf(x) (dt[bid[x]]<B?nxt[x]:max(1, fa[x]-dt[bid[x]]))
inline int lca(int x, int y){
while(gf(x)^gf(y)){
if(x<y) y=gf(y);
else x=gf(x);
}
if(bid[x]!=bid[y]) return gf(x);
while(x^y){
if(x<y) y=max(1, fa[y]-dt[bid[y]]);
else x=max(1, fa[x]-dt[bid[x]]);
}
return x;
}
inline int dep(int x){
int ret=0;
while(x^1){
if(dt[bid[x]]<B) ret+=dis[x], x=nxt[x];
else ++ret, x=max(1, fa[x]-dt[bid[x]]);
}
return ret;
}
inline int getd(int x, int y){
if(x==y) return 0;
return dep(x)+dep(y)-2*dep(lca(x, y));
}
inline int jump(int x, int t){
while(true) {
while(gf(x)>t) x=gf(x);
if(max(1, fa[x]-dt[bid[x]])>t) x=max(1, fa[x]-dt[bid[x]]);
else return x;
}
}
inline bool cmp(int x, int y){
if(x==y) return false;
int t=lca(x, y);
if(t==x) return true;
if(t==y) return false;
return jump(x, t)<jump(y, t);
}
int vec[N], vec2[N], sz, p1, p2, it;
inline void work(int l, int r){
if(l==r) return ;
int mid=(l+r)>>1;
work(l, mid); work(mid+1, r);
p1=l; p2=mid+1; it=l;
while(p1<=mid||p2<=r){
if(p1>mid){
vec2[it++]=vec[p2++];
}
else if(p2>r){
vec2[it++]=vec[p1++];
}
else{
if(cmp(vec[p1], vec[p2])) vec2[it++]=vec[p1++];
else vec2[it++]=vec[p2++];
}
}
for(int i=l; i<=r; ++i) vec[i]=vec2[i];
}
int main(){
// freopen("D:\\nya\\acm\\B\\test.in","r",stdin);
// freopen("D:\\nya\\acm\\B\\test.out","w",stdout);
read(n); read(m);
for(int i=2; i<=n; ++i) read(fa[i]);
for(int i=2; i<=n; ++i) bid[i]=(i-2)/B+1;
bid[1]=0;
lp[0]=rp[0]=1; dt[0]=B;
for(int i=1; i<=bid[n]; ++i) lp[i]=rp[i-1]+1, rp[i]=rp[i-1]+B;
rp[bid[n]]=n;
for(int i=1; i<=bid[n]; ++i) rebuild(i);
while(m--){
int op; read(op);
if(op==1){
int l, r, d; read(l); read(r); read(d);
if(bid[l]==bid[r]){
for(int i=l; i<=r; ++i) fa[i]-=d;
rebuild(bid[l]);
continue;
}
for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d;
rebuild(bid[l]);
for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d;
rebuild(bid[r]);
for(int i=bid[l]+1; i<bid[r]; ++i){
dt[i]+=d; dt[i]=min(dt[i], n); rebuild(i);
}
}
else{
int k, x;
read(k);
if(k==0){
printf("0\n");
continue;
}
sz=0;
while(k--){
read(x); if(!ins[x]) vec[++sz]=x, ins[x]=1;
}
work(1, sz);
vec[0]=vec[sz];
int ans=0;
for(int i=1; i<=sz; ++i) ans+=getd(vec[i-1], vec[i]);
ans>>=1;
for(auto t:vec) ins[t]=0;
printf("%d\n", ans+1);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7896kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 1655ms
memory: 8044kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 78 70 64 60 55 60 58 52 54 51 53 56 51 51 57 55 52 49 55 49 50 53 49 49 48 49 48 53 50 50 54 47 52 45 49 49 46 47 48 49 50 48 49 47 48 47 49 48 50 48 49 48 47 49 48 51 48 48 45 45 46 50 50 50 48 49 46 47 47 46 48 48 47 49 47 46 47 46 47 46 45 47 49 49 50 51 48 48 49 47 47 48 50 46 47 48 50 46 47 ...
result:
ok 13214 lines
Test #4:
score: -100
Time Limit Exceeded
input:
6173 198631 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2819 1049 1155 831 722 5962 123 624 554 601 241 597 81 29 34 390 350 443 385 6038 6083 258 5 315 27 281 6029 300 6136 322 227 46 271 263 26 268 257 6101 5816 255 258 156 243 270 186 6099 16 13 5435 163 7 35 219 182 214 10 24 23 194 178 188 183 200 167 158 197 24 189 131 35 167 24 189 15 183 176 6050...