QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246197#7626. Quake and Rebuilducup-team1447#WA 74ms5664kbC++142.7kb2023-11-10 17:09:552023-11-10 17:09:56

Judging History

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

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

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()
{
	top=0;
	int k=read();
	int res=0;
	For(i,1,k){
		int x=read();
		if(vis[x])continue;
		add(x);
	}
	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)break;
		}
		now=now2;
		buc[i].clear();
	}
	For(i,1,top) vis[st[i]]=0; top=0;
	cout<<res+1<<"\n";
}

signed main()
{
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5448kb

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: 74ms
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: -100
Wrong Answer
time: 68ms
memory: 5664kb

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
1154
830
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:

wrong answer 3rd lines differ - expected: '1155', found: '1154'