QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1218 | #274992 | #7626. Quake and Rebuild | rotcar07 | ship2077 | Failed. | 2024-11-20 20:20:22 | 2024-11-20 20:20:27 |
Details
Extra Test:
Accepted
time: 2840ms
memory: 15048kb
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:
ok 200000 lines
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#274992 | #7626. Quake and Rebuild | ship2077 | AC ✓ | 1945ms | 15308kb | C++14 | 2.3kb | 2023-12-04 10:09:44 | 2024-11-20 20:29:11 |
answer
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
constexpr int M=2e5+5; bool flag[M],vis[M],cur[M];
int n,m,x,y,op,mn,ans,tp,block,bel[M];
int L[M],R[M],fa[M],jump[M],dep[M],lazy[M];vector<int>node[M];
int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
return x*f;
}
void rebuild(int x){ flag[x]=1;
for (int i=L[x];i<=R[x];i++) fa[i]=max(fa[i]-lazy[x],1);
for (int i=L[x];i<=R[x];i++)
if (fa[i]<L[x]) jump[i]=fa[i],dep[i]=1;
else jump[i]=jump[fa[i]],dep[i]=dep[fa[i]]+1,flag[x]=0;
lazy[x]=0;
}
void upd1(int l,int r,int c){
for (int i=l;i<=r;i++) fa[i]=max(fa[i]-c,1);
rebuild(bel[l]);
}
void upd2(int l,int r,int c){
for (int i=l+1;i<r;i++){lazy[i]+=c;
if (lazy[i]>R[i]) lazy[i]=R[i];
if (!flag[i]) rebuild(i);
}
}
void update(int l,int r,int c){
if (bel[l]==bel[r]) return upd1(l,r,c),void();
upd1(l,R[bel[l]],c);upd2(bel[l],bel[r],c);upd1(L[bel[r]],r,c);
}
int Jump(int x){return max(1,jump[x]-lazy[bel[x]]);}
int Fa(int x){return max(1,fa[x]-lazy[bel[x]]);}
void insert(int x){
if (vis[x]) return ;
node[bel[x]].push_back(x);
vis[x]=1;mn=min(mn,x);
}
void build(int k){ ans=1;mn=n;
while (k--) insert(read());
for (int i=bel[n];i;i--)
if (!node[i].empty()){ bool fl=0;
for (auto x:node[i]){
const int tmp=Jump(x);
fl|=vis[tmp]||cur[tmp];cur[tmp]=1;
}
for (auto x:node[i]) cur[x]=0;
if (!fl){
if (node[i].size()==1&&node[i][0]==mn) break;
for (auto x:node[i]){
const int tmp=Jump(x);
ans+=dep[x];insert(tmp);
}
continue;
}
for (int j=R[i];j>=L[i];j--)
if (vis[j]){
if (j==mn) break;
ans++;insert(Fa(j));
}
}
for (int i=0;i<=bel[n];i++){
for (auto x:node[i]) vis[x]=0;
node[i].clear();
}
printf("%d\n",ans);
}
int main(){
n=read();m=read();
for (int i=2;i<=n;i++) fa[i]=read();
block=max(2,(int)ceil(sqrt(n)));
for (int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
for (int i=1;i<=bel[n];i++) L[i]=R[i-1]+1,R[i]=R[i-1]+block;
L[1]=2;R[bel[n]]=n;
for (int i=1;i<=bel[n];i++) rebuild(i);
while (m--){
op=read();x=read();
if (op==1) y=read(),update(x,y,read());
if (op==2) build(x);
}
return 0;
}