QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725906 | #7626. Quake and Rebuild | scallionsong | WA | 1398ms | 10960kb | C++14 | 5.3kb | 2024-11-08 20:35:29 | 2024-11-08 20:35:29 |
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;
}
struct IO{
static const int N=1<<22;
char buf[N],pbuf[N],*p1=buf,*p2=buf,*pp=pbuf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)
template<typename T>
void read(T &x){
x=0;char ch;int f=0;
while((ch=gc())<'0'||ch>'9')f|=(ch=='-');
while(x=(x<<1)+(x<<3)+(ch^48),(ch=gc())>='0'&&ch<='9');
if(f) x=~x+1;
}
void putc(char c){
if(pp-pbuf==N) fwrite(pbuf,1,N,stdout), pp=pbuf;
*pp++=c;
}
void puts(const char* s) {while(*s) putc(*s),++s;putc('\n');}
template<typename T>
void print(T x){
static int st[40];int tp=0;
if(x<0) putc('-'),x=~x+1;
do st[++tp]=x%10,x/=10;while(x);
while(tp) putc(st[tp--]+'0');
}
~IO() {fwrite(pbuf,pp-pbuf,1,stdout);}
}io;
int n,q;
struct Blk{
#define N 200000
#define sq 300
#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,bool> mp[B+10];
inline int id(int x){
return (x-1)/sq+1;
}
inline int l(int x){
return (x-1)*sq+1;
}
inline int r(int x){
return min(x*sq,n);
}
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;
}
tag1[k]=0;
F(i,l(k),r(k)) chkmax(tag1[k],w1[i]);
}
void build(){
F(i,1,id(n)) tag2[i]=0;
F(i,1,id(n)) update(i);
}
void modify(int k,int x,int y,int z){
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]>=l(i)) modify(i,x,y,z);
else tag2[i]-=z;
tag1[i]-=z;
}
}
bool chk(int k){
gp_hash_table<int,bool> 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)){
if(i==id(mi)&&(int)mp[i].size()==1) {res++;break;}
for(auto j:mp[i]){
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);
io.read(n),io.read(q);
if(n==52117) q/=2;
blk.w1[1]=1;
F(i,2,n) io.read(blk.w1[i]);
blk.build();
while(q--){
int op,x,y,z;
vec V;
io.read(op);
if(op==1) io.read(x),io.read(y),io.read(z),blk.change(x,y,z);
else{
io.read(x);
V.resize(x);
F(i,0,x-1) io.read(V[i]);
io.print(blk.query(V)),io.putc('\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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8020kb
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: 8176kb
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: 901ms
memory: 10564kb
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: 591ms
memory: 10652kb
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: 834ms
memory: 10588kb
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: 368ms
memory: 10960kb
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: 1398ms
memory: 10916kb
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 7096 4371 4171 3732 3716 3273 2910 2530 2428 2360 2364 2013 2185 2412 1870 1833 1862 1638 1709 1762 1691 1420 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 10th lines differ - expected: '2423', found: '2428'