QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #726052 | #7626. Quake and Rebuild | scallionsong | Compile Error | / | / | C++14 | 7.5kb | 2024-11-08 21:25:25 | 2024-11-08 21:25:25 |
Judging History
你现在查看的是最新测评结果
- [2024-11-20 20:27:49]
- hack成功，自动添加数据
- (/hack/1219)
- [2024-11-08 21:25:25]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2024-11-08 21:25:25]
- 提交
answer
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
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 400
#define B N/sq
bool vis[N+10];
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 tag1[i]-=z,tag2[i]-=z;
}
}
bool chk(int k){
bool res=1;
int tot=0;
vec V;
V.resize(mp[k].size());
for(auto i:mp[k]) V[tot++]=max(w2[i.fir]+tag2[k],1);
for(auto i:V){
if(vis[i]) {res=0;break;}
vis[i]=1;
}
for(auto i:V) vis[i]=0;
return res;
// 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].find(j)==mp[i].end()) 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=150000;
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
answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
answer.code:81:25: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
81 | inline void inc(T &a,T b){
| ^
answer.code:81:25: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:81:25: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:81:25: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:87:25: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
87 | inline void dec(T &a,T b){
| ^
answer.code:87:25: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:87:25: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:87:25: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:93:25: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
93 | inline void muc(T &a,T b){
| ^
answer.code:93:25: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:93:25: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:93:25: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:97:28: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
97 | inline bool chkmin(T &a,T b){
| ^
answer.code:97:28: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:97:28: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:97:28: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:103:28: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
103 | inline bool chkmax(T &a,T b){
| ^
answer.code:103:28: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:103:28: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:103:28: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:113:23: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
113 | void read(T &x){
| ^
answer.code:113:23: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:113:23: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:113:23: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:119:25: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
119 | void putc(char c){
| ^
answer.code:119:25: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:119:25: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:119:25: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:123:32: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
123 | void puts(const char* s) {while(*s) putc(*s),++s;putc('\n');}
| ^
answer.code:123:32: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:123:32: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:123:32: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:125:23: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
125 | void print(T x){
| ^
answer.code:125:23: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:125:23: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:125:23: wa...