QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1219 | #645378 | #7626. Quake and Rebuild | rotcar07 | Displace_ | Success! | 2024-11-20 20:26:18 | 2024-11-20 20:26:19 |
Details
Extra Test:
Time Limit Exceeded
input:
200000 200000 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 9...
output:
200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000 200000...
result:
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645378 | #7626. Quake and Rebuild | Displace_ | TL | 2756ms | 9172kb | C++14 | 3.2kb | 2024-10-16 18:01:00 | 2024-11-20 20:31:16 |
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=600;
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);
}
bool occ[N];
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, fa[i]=max(fa[i], 0);
rebuild(bid[l]);
continue;
}
for(int i=l; i<=rp[bid[l]]; ++i) fa[i]-=d, fa[i]=max(fa[i], 0);
rebuild(bid[l]);
for(int i=lp[bid[r]]; i<=r; ++i) fa[i]-=d, fa[i]=max(fa[i], 0);
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;
}
vector<int> vec;
while(k--){
read(x); if(!ins[x]) vec.ep(x), ins[x]=1;
}
if(vec.size()>=B){
int lc=vec[0];
for(auto t:vec) lc=lca(lc, t);
int ans=1;
for(int i=n; i>lc; --i) if(ins[i]) ++ans, ins[max(1, fa[i]-dt[bid[i]])]=1, ins[i]=0;
ins[lc]=0;
printf("%d\n", ans);
continue;
}
sort(vec.begin(), vec.end(), cmp);
vec.ep(vec[0]);
int ans=0;
for(int i=1; i<(int)vec.size(); ++i) ans+=getd(vec[i-1], vec[i]);
ans>>=1;
for(auto t:vec) ins[t]=0;
printf("%d\n", ans+1);
}
}
return 0;
}