QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725820 | #7626. Quake and Rebuild | scallionsong | WA | 1748ms | 5316kb | C++14 | 4.5kb | 2024-11-08 20:11:45 | 2024-11-08 20:11:45 |
Judging History
answer
bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define Pdb pair<db,db>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const int INF=0x3f3f3f3f;
const int Mod=998244353;
template<typename T>
inline void inc(T &a,T b){
if(b<0) b+=Mod;
a+=b;
if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
if(b<0) b+=Mod;
a-=b;
if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
if(a<=b) return false;
a=b;
return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
if(a>=b) return false;
a=b;
return true;
}
int n,q;
struct Blk{
#define N 200000
#define sq 100
#define B N/sq
int w1[N+10],w2[N+10],w3[N+10];
int tag1[B+10],tag2[B+10];
gp_hash_table<int,int> mp[B+10];
int id(int x){
return (x-1)/sq+1;
}
int l(int x){
return (x-1)*sq+1;
}
int r(int x){
return min(x*sq,n);
}
void down(int k){
F(i,l(k),r(k)) w1[i]+=tag2[k];
tag2[k]=0;
}
void update(int k){
F(i,l(k),r(k)){
if(id(w1[i])!=k) w2[i]=w1[i],w3[i]=1;
else w2[i]=w2[w1[i]],w3[i]=w3[w1[i]]+1;
}
}
void build(){
F(i,1,id(n)) update(i);
}
void modify(int k,int x,int y,int z){
down(k);
F(i,l(k),r(k)) if(i>=x&&i<=y) w1[i]=max(w1[i]-z,1);
update(k);
}
void change(int x,int y,int z){
if(id(x)==id(y)){
modify(id(x),x,y,z);
return;
}
modify(id(x),x,y,z),modify(id(y),x,y,z);
F(i,id(x)+1,id(y)-1){
if(tag1[i]<sq) modify(i,x,y,z);
else tag2[i]-=z;
// tag1[i]+=z;
}
}
bool chk(int k){
gp_hash_table<int,int> tg;
for(auto i:mp[k]){
int nxt=max(w2[i.fir]+tag2[k],1);
if(tg[nxt]) return 0;
tg[nxt]=1;
}
return 1;
}
int query(vec V){
F(i,1,id(n)) mp[i].clear();
int mi=INF;
for(auto i:V) mp[id(i)][i]=1,chkmin(mi,i);
int res=0;
UF(i,id(n),1){
if(mp[i].empty()) continue;
if(chk(i)){
for(auto j:mp[i]){
if(j.fir==mi) {res++;break;}
res+=w3[j.fir];
int nxt=max(w2[j.fir]+tag2[i],1);
mp[id(nxt)][nxt]=1;
chkmin(mi,nxt);
}
}
else{
UF(j,r(i),l(i)){
if(!mp[i][j]) continue;
if(j==mi) {res++;break;}
res++;
int nxt=max(w1[j]+tag2[i],1);
mp[id(nxt)][nxt]=1;
chkmin(mi,nxt);
}
}
}
return res;
}
#undef N
#undef sq
#undef B
}blk;
bool M2;
int main(){
// freopen("aminusb.in","r",stdin);
// freopen("aminusb.out","w",stdout);
srand(time(0)^(*new int));
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
blk.w1[1]=1;
F(i,2,n) cin>>blk.w1[i];
blk.build();
while(q--){
int op,x,y,z;
vec V;
cin>>op;
if(op==1) cin>>x>>y>>z,blk.change(x,y,z);
else{
cin>>x;
V.resize(x);
F(i,0,x-1) cin>>V[i];
cout<<blk.query(V)<<'\n';
}
}
look_memory;
look_time;
return 0;
}
/*
g++ B1.cpp -o B1 -std=c++14 -O2&&./B1
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
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
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4268kb
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: 4404kb
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: 891ms
memory: 4536kb
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: 909ms
memory: 4784kb
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: 1193ms
memory: 4496kb
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: -100
Wrong Answer
time: 1748ms
memory: 5316kb
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 134 12761 5309 1646 12726 1882 247 78 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 2...
result:
wrong answer 5th lines differ - expected: '211', found: '134'