QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642246 | #7626. Quake and Rebuild | fryan | TL | 540ms | 3796kb | C++17 | 2.3kb | 2024-10-15 12:19:51 | 2024-10-15 12:19:52 |
Judging History
answer
#pragma once
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const int mxn = 2e5+5;
const int bsz = 300; //change
const int nbk = mxn/bsz+1;
int n,m;
int fa[mxn];
int nx[mxn];
int lz[nbk];
inline int nex(int v) {
if (lz[v/bsz] >= bsz) {
return max(fa[v]+lz[v/bsz],0);
}
return nx[v];
}
inline void manual_update(int v) {
int f = max(fa[v]+lz[v/bsz],0);
if (f/bsz != v/bsz) {
nx[v] = f;
} else {
nx[v] = nex(f);
}
}
int lca(int a, int b) {
while (1) {
if (a < b) swap(a,b);
//a > b
int na = nex(a);
int nb = nex(b);
if (na != nb) {
a = na;
} else {
break;
}
}
while (1) {
if (a==b) return a;
if (a < b) swap(a,b);
a = max(fa[a]+lz[a/bsz],0);
}
exit(1);
}
void quake(int l, int r, int d) {
for (int i=l; i%bsz && i<=r; i++) {
fa[i] -= d;
manual_update(i);
}
int lb = (l+bsz-1)/bsz;
int rb = r/bsz-1;
for (int i=lb; i<=rb; i++) {
lz[i] -= d;
if (-lz[i] < bsz) {
//manual update
for (int j=i*bsz; j<(i+1)*bsz; j++) {
manual_update(j);
}
}
}
//do right update
if (r/bsz != l/bsz) {
for (int i=bsz*(r/bsz); i<=r; i++) {
fa[i] -= d;
manual_update(i);
}
}
}
void rebuild(vector<int> &val) {
set<int> ans;
sort(all(val));
val.erase(unique(all(val)),val.end());
for (int i=0; i<sz(val); i++) {
for (int j=i+1; j<sz(val); j++) {
int R = lca(val[i],val[j]);
int v = val[i];
ans.insert(R);
while (v != R) {
ans.insert(v);
v = max(fa[v]+lz[v/bsz],0);
}
v = val[j];
while (v != R) {
ans.insert(v);
v = max(fa[v]+lz[v/bsz],0);
}
}
}
cout<<sz(ans)<<"\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m;
for (int i=1; i<n; i++) {
cin>>fa[i]; --fa[i];
}
//build nx
for (int i=0; i<n; i++) {
if (fa[i]/bsz == i/bsz) {
nx[i] = nx[fa[i]];
} else {
nx[i] = fa[i];
}
}
while (m--) {
int t; cin>>t;
if (t==1) {
//quake
int l,r,d; cin>>l>>r>>d;
quake(l-1,r-1,d);
} else {
int k; cin>>k;
vector<int> val;
for (int i=0; i<k; i++) {
int x; cin>>x; --x;
val.push_back(x);
}
rebuild(val);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
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: 0ms
memory: 3764kb
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: 540ms
memory: 3796kb
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 ...