QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#151024 | #6805. Data Structure | do_while_true# | WA | 11178ms | 349932kb | C++20 | 3.1kb | 2023-08-26 14:59:54 | 2023-08-26 14:59:55 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
#include<random>
#include<functional>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define dbg(x) cerr<<"In the line "<<__LINE__<<" the "<<#x<<" = "<<x<<'\n'
#define dpi(x,y) cerr<<"In the line "<<__LINE__<<" the "<<#x<<" = "<<x<<" the "<<#y<<" = "<<y<<'\n';
typedef long long ll;
typedef vector<int> vi;
template<typename T>T &read(T &r){
r=0;bool w=0;char ch=getchar();
while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9')r=r*10+ch-'0',ch=getchar();
return r=w?-r:r;
}
inline int lowbit(int x){return x&(-x);}
const int N=300010;
const int B=100;//
int n,m;
int fa[N];
vi eg[N];
int dep[N],L[N],R[N],dft,mx;
int rk[N];
vi vec[N],tree[N];
vi pos[201][201],tr[201][201];
void modify(int o,int x,int v){
int k=tree[o].size();--k;
for(;x<=k;x+=lowbit(x))tree[o][x]+=v;
}
int query(int o,int x){
int s=0;for(;x;x-=lowbit(x))s+=tree[o][x];
return s;
}
void modify(int u,int v,int x,int w){
int k=tr[u][v].size();--k;
for(;x<=k;x+=lowbit(x))tr[u][v][x]+=w;
}
int query(int u,int v,int x){
int s=0;for(;x;x-=lowbit(x))s+=tr[u][v][x];
return s;
}
void dfs(int x){
L[x]=++dft;mx=max(mx,dep[x]);rk[dft]=x;
vec[dep[x]].pb(dft);
for(int i=1;i<=B;i++)pos[i][dep[x]%i].pb(dft);
for(auto v:eg[x]){
dep[v]=dep[x]+1;
dfs(v);
}
R[x]=dft;
}
void solve(){
read(n);read(m);
for(int i=1;i<=n;i++)vi().swap(eg[i]),vi().swap(vec[i]);
for(int i=2;i<=n;i++)read(fa[i]),eg[fa[i]].pb(i);
for(int i=1;i<=B;i++)
for(int j=0;j<i;j++)
vi().swap(pos[i][j]);
mx=0;
dep[1]=1;dfs(1);
for(int i=1;i<=mx;i++){
vi().swap(tree[i]);
tree[i].resize(vec[i].size()+1);
}
for(int i=1;i<=B;i++)
for(int j=0;j<i;j++){
vi().swap(tr[i][j]);
tr[i][j].resize(pos[i][j].size()+1);
}
auto LB=[&](const vi &ve,int &x){
return lower_bound(ve.begin(),ve.end(),x)-ve.begin();
};
auto UB=[&](const vi &ve,int &x){
return upper_bound(ve.begin(),ve.end(),x)-ve.begin();
};
for(int o=1;o<=m;o++){
int op;read(op);
if(o%1000==0)cerr<<o<<' ';
if(op==1){
int a,x,y,z;read(a);read(x);read(y);read(z);
if(x>B){
for(int i=dep[a]+y;i<=mx;i+=x){
int l=LB(vec[i],L[a]);
int r=UB(vec[i],R[a])-1;
++l;++r;
if(l<=r){
modify(i,l,z);
modify(i,r+1,-z);
}
else break;
}
}
else{
y=(y+dep[a])%x;
int l=LB(pos[x][y],L[a]);
int r=UB(pos[x][y],R[a])-1;
++l;++r;
if(l<=r){
// dpi(l,r);
// dpi(rk[pos[x][y][l-1]],rk[pos[x][y][r-1]]);
modify(x,y,l,z);
modify(x,y,r+1,-z);
}
}
}
else{
int a;read(a);
int p=LB(vec[dep[a]],L[a]);
int s=query(dep[a],p+1);
for(int i=1;i<=B;i++){
s+=query(i,dep[a]%i,LB(pos[i][dep[a]%i],L[a])+1);
}
cout << s << '\n';
}
}
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int T;read(T);
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 31400kb
input:
1 5 5 1 1 2 1 1 1 5 4 1 1 1 4 1 5 1 2 1 0 4 2 3 2 1
output:
5 0
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 11178ms
memory: 349932kb
input:
4 300000 300000 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...
output:
1130 1509 2343 2426 4524 5096 8031 10312 15081 15081 0 21803 28276 507 29392 31408 31656 36062 507 37628 40202 45396 47064 48157 48157 50507 50866 60827 63565 0 398 71612 398 73533 76075 76524 398 78559 81801 1205 94975 1205 104994 106433 109726 110163 115355 116799 118169 119008 119008 398 120377 1...
result:
wrong answer 29908th lines differ - expected: '6777', found: '6597'