QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246227#7626. Quake and Rebuilducup-team1447#WA 122ms7968kbC++143.0kb2023-11-10 17:33:412023-11-10 17:33:43

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2023-11-10 17:33:43]
  • 评测
  • 测评结果:WA
  • 用时:122ms
  • 内存:7968kb
  • [2023-11-10 17:33:41]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m,a[maxn];

int B,t,L[1005],R[1005],bel[maxn],tag[1005],go[maxn],god[maxn];
void build(int id)
{
	For(i,L[id],R[id]){
		int v=max(1,a[i]-tag[id]);
		if(v<L[id])go[i]=v,god[i]=1;
		else go[i]=go[v],god[i]=god[v]+1;
	}
}

void mdf(int l,int r,int x)
{
	int bl=bel[l],br=bel[r];
	if(bl==br){
		For(i,l,r)a[i]=max(1,a[i]-x);
		build(bl);
		return;
	}
	For(i,l,R[bl])a[i]=max(1,a[i]-x);
	For(i,L[br],r)a[i]=max(1,a[i]-x);
	build(bl),build(br);
	For(i,bl+1,br-1){
		tag[i]=min(tag[i]+x,n);
		if(tag[i]<B)build(i);
	}
}

pii pre(int p){
	int b=bel[p];
	if(tag[b]<B)return mkp(go[p],god[p]);
	return mkp(max(a[p]-tag[b],1),1);
}
int getfa(int p){
	return max(1,a[p]-tag[bel[p]]);
}

vi buc[1005];
bool vis[maxn];
int st[maxn],top;
void add(int x){
	st[++top]=x;
	vis[x]=1;
	buc[bel[x]].pb(x);
}
bool vis2[maxn];
void query()
{
//	For(i,1,t)buc[i].clear();
//	For(i,1,n)vis[i]=0;
	
	top=0;
	int k=read();
	int res=0;
	For(i,1,k){
		int x=read();
		if(vis[x])continue;
		add(x);
	}
	
//	For(i,1,n)cout<<getfa(i)<<" "; cout<<" fa\n";
//	For(i,1,n)cout<<pre(i).fi<<" "; cout<<" pre\n";
	
	int now=top;
	Rep(i,t,1){
		if(now==1){
			For(j,1,i) buc[j].clear();
			break;
		}
		bool hav=0;
		int now2=now-buc[i].size();
		for(int x:buc[i]){
			pii tmp=pre(x);
			if(!vis[tmp.fi]) add(tmp.fi),++now2;
			else hav=1;
		}
		if(!hav){
			for(int x:buc[i]) res+=pre(x).se;
		}else{
			bool del=0,ok=0;
			Rep(j,R[i],L[i]) if(vis[j]) {
				++res;
				int up=getfa(j);
				vis[j]=0;
				--now;
				if(up<L[i]) ok=1;
				else if(!vis[up]) vis[up]=1,++now;
				if(now==1 && !ok){
					del=1;
					break;
				}
			}
			if(del){
				For(j,L[i],R[i]) vis[j]=0;
				For(j,1,i) buc[i].clear();
				break;
			}
		}
		now=now2;
		buc[i].clear();
	}
	For(i,1,top) vis[st[i]]=0; top=0;
	cout<<res+1<<"\n";
}

signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read(),m=read();
	For(i,2,n)a[i]=read();
	B=sqrt(n);
	t=(n-2)/B+1;
	For(i,1,t)L[i]=(i-1)*B+2,R[i]=min(n,i*B+1),build(i);
	For(i,1,t)For(j,L[i],R[i])bel[j]=i;
	For(_,1,m){
		int o=read();
		if(o==1){
			int l=read(),r=read(),d=read();
			mdf(l,r,d);
		}else{
			query();
		}
	}
	return 0;
}
/*
12 4094
1 2 2 3 3 3 7 4 5 1 10 
2 3 1 3 4 
2 3 2 3 4 
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5472kb

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: 1ms
memory: 3468kb

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: 72ms
memory: 5620kb

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: 0
Accepted
time: 66ms
memory: 5708kb

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 ...

output:

2819
1049
1155
831
722
5962
123
624
554
601
241
597
81
29
34
390
350
443
385
6038
6083
258
5
315
27
281
6029
300
6136
322
227
46
271
263
26
268
257
6101
5816
255
258
156
243
270
186
6099
16
13
5435
163
7
35
219
182
214
10
24
23
194
178
188
183
200
167
158
197
24
189
131
35
167
24
189
15
183
176
6050...

result:

ok 30261 lines

Test #5:

score: 0
Accepted
time: 98ms
memory: 7968kb

input:

9724 198809
1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...

output:

24
25
31
31
27
25
29
23
23
21
26
23
21
24
23
23
26
26
21
24
27
23
23
23
20
19
20
18
28
25
26
21
19
21
21
26
20
23
17
20
18
21
22
22
18
21
25
18
17
18
24
18
16
18
19
24
20
18
19
17
17
21
25
19
21
23
19
23
15
17
19
19
22
18
20
18
21
19
18
18
15
16
22
17
17
18
13
16
19
16
15
16
18
16
15
17
15
18
18
20
...

result:

ok 66269 lines

Test #6:

score: 0
Accepted
time: 68ms
memory: 5628kb

input:

12796 185791
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...

output:

12100
7532
12357
12774
211
12761
5309
1646
12726
1882
247
118
1660
12229
12143
1499
1368
1273
1387
341
274
1374
1237
1359
112
1152
981
12681
949
890
820
774
62
644
836
925
12
13
1203
666
732
731
1127
12320
11473
82
655
12788
569
5866
621
2798
12114
85
609
11827
1
12455
56
605
575
530
54
645
1845
93
...

result:

ok 3210 lines

Test #7:

score: -100
Wrong Answer
time: 122ms
memory: 5740kb

input:

16122 194030
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...

output:

9730
7016
4371
4171
3732
3716
3273
2910
2530
2423
2366
2351
2013
2196
2430
1891
1833
1852
1638
1709
1762
1699
1423
1295
1471
1255
1356
1428
1214
1191
1066
1104
1131
1116
1010
860
964
949
927
994
879
829
718
787
786
754
757
795
820
739
761
689
659
658
587
663
654
658
631
593
633
583
575
598
554
579
4...

result:

wrong answer 2nd lines differ - expected: '7096', found: '7016'