QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246227 | #7626. Quake and Rebuild | ucup-team1447# | WA | 122ms | 7968kb | C++14 | 3.0kb | 2023-11-10 17:33:41 | 2023-11-10 17:33:43 |
Judging History
你现在查看的是最新测评结果
- [2024-11-20 20:27:49]
- hack成功,自动添加数据
- (/hack/1219)
- [2023-12-04 09:28:18]
- hack成功,自动添加数据
- (//qoj.ac/hack/477)
- [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'