QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246201 | #7626. Quake and Rebuild | ucup-team1447# | WA | 79ms | 7512kb | C++14 | 2.7kb | 2023-11-10 17:15:20 | 2023-11-10 17:15:20 |
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:15:20]
- 提交
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){
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()
{
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: 5344kb
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: 5488kb
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: 79ms
memory: 7512kb
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: 70ms
memory: 5740kb
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'