QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#151024#6805. Data Structuredo_while_true#WA 11178ms349932kbC++203.1kb2023-08-26 14:59:542023-08-26 14:59:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-26 14:59:55]
  • 评测
  • 测评结果:WA
  • 用时:11178ms
  • 内存:349932kb
  • [2023-08-26 14:59:54]
  • 提交

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'