QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #864311 | #9311. Protection War | niucard | Compile Error | / | / | C++20 | 6.8kb | 2025-01-20 14:33:24 | 2025-01-20 14:33:24 |
Judging History
answer
#include<bits/stdc++.h>
#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")
#pragma GCC optimize(2)
using namespace std;
int n,q,a[300010],len,l[1010],r[1010],id[300010];
long long b1[1010],b2[1010],c[300010];
struct node
{
mutable int first,second;
bool operator < (const node &x)const
{
if(first==x.first)
return second<x.second;
return first<x.first;
}
};
set<node> s;
void Add(int L,int R,long long y)
{
b2[id[L]]-=c[L]*L,b2[id[R+1]]-=c[R+1]*(R+1);
c[L]+=y,c[R+1]-=y;
b1[id[L]]+=y,b1[id[R+1]]-=y;
b2[id[L]]+=c[L]*L,b2[id[R+1]]+=c[R+1]*(R+1);
}
long long ask(int L,int R)
{
long long num=0;
for(int i=1;i<id[R];i++)
{
num+=b1[i]*(R+1)-b2[i];
if(i<id[L-1])
num-=b1[i]*L-b2[i];
}
for(int i=l[id[L-1]];i<L;i++)
num-=L*c[i]-i*c[i];
for(int i=l[id[R]];i<=R;i++)
num+=(R+1)*c[i]-i*c[i];
return num;
}
void bh()
{
set<node>::iterator it=s.begin();
while(it!=s.end())
{
node x=(*it);
if(x.second!=n)
{
Add(x.second,x.second,-ask(x.second,x.second));
if(x.first==x.second)
it=s.erase(it);
else
(*it).second--;
}
else
it++;
}
}
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
int main()
{
// freopen("cin.in","r",stdin);
// freopen("out.out","w",stdout);
memset(l,0x3f,sizeof l);
fin>>n>>q;
len=512;
for(int i=1;i<=n;i++)
{
id[i]=(i-1)/len+1;
l[id[i]]=min(l[id[i]],i),r[id[i]]=max(r[id[i]],i);
}
for(int i=1;i<=n;i++)
{
fin>>a[i];
Add(i,i,a[i]);
}
s.insert((node){1,n});
while(q--)
{
int op;
fin>>op;
if(op==1)
{
int x,y;
fin>>x>>y;
Add(x,x,y-ask(x,x));
if(y)
{
set<node>::iterator it=s.upper_bound(node{x,1e9}),itt;
if(it!=s.begin())
it--;
else
{
if(it==s.end()||(*it).first>x+1)
s.insert(node{x,x});
else
{
int R=(*it).second;
s.erase(it);
s.insert(node{x,R});
}
bh();
continue;
}
if((*it).second>=x)
{
bh();
continue;
}
itt=it,it++;
node x1=(*itt),x2=(*it);
if(x1.second+1==x&&x2.first-1==x)
{
it++;
s.erase(itt,it);
s.insert(node{x1.first,x2.second});
}
else if(x1.second+1==x)
{
s.erase(itt);
s.insert(node{x1.first,x});
}
else if(x2.first-1==x)
{
s.erase(it);
s.insert(node{x,x2.second});
}
else
s.insert(node{x,x});
}
else
{
set<node>::iterator it=s.upper_bound(node{x,1e9}),itt;
if(it!=s.begin())
it--;
else
{
bh();
continue;
}
if((*it).second<x)
{
bh();
continue;
}
node x1=(*it);
s.erase(it);
if(x1.first==x)
{
if(x1.first!=x1.second)
s.insert(node{x1.first+1,x1.second});
}
else if(x1.second==x)
s.insert(node{x1.first,x1.second-1});
else
{
s.insert(node{x1.first,x-1});
s.insert(node{x+1,x1.second});
}
}
}
else if(op==2)
{
int L,R,v;
fin>>L>>R>>v;
Add(L,R,v);
set<node>::iterator it1=s.lower_bound(node{L,0}),it2=s.upper_bound(node{R,1e9}),it3;
if(it2!=s.begin())
{
it3=it2;
it3--;
R=max(R,(*it3).second);
}
s.erase(it1,it2);
it1=(s.insert(node{L,R})).first;
if(it1!=s.begin())
{
it2=it1;
it1--;
node x=(*it1);
if(x.second>=L-1)
{
it2++;
s.erase(it1,it2);
it1=(s.insert(node{x.first,R})).first;
}
else
it1=it2;
}
it2=it1,it1++;
if(it1!=s.end())
{
node x=(*it1),y=(*it2);
if(x.first<=R+1)
{
it1++;
s.erase(it2,it1);
s.insert(node{y.first,x.second});
}
}
}
else if(op==3)
{
for(set<node>::iterator it=s.begin();it!=s.end();it++)
{
node x=(*it);
Add(x.first,x.second,1);
}
}
else if(op==4)
{
for(set<node>::iterator it=s.begin();it!=s.end();it++)
{
node x=(*it);
Add(x.first,x.second,x.second-x.first+1);
}
}
else
{
int L,R;
fin>>L>>R;
fout<<ask(L,R);
fout.pc('\n');
}
bh();
}
return 0;
}
Details
answer.code:23:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
23 | #pragma GCC optimize("-fwhole-program")
| ^
answer.code:30:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
30 | #pragma GCC optimize("-fstrict-overflow")
| ^
answer.code:32:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
32 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
answer.code:46:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
46 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
answer.code:56:40: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
56 | bool operator < (const node &x)const
| ^~~~~
answer.code:56:40: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:56:40: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:56:40: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:64:33: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
64 | void Add(int L,int R,long long y)
| ^
answer.code:64:33: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:64:33: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:64:33: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:26: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
71 | long long ask(int L,int R)
| ^
answer.code:71:26: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:26: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:71:26: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:9: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
86 | void bh()
| ^
answer.code:86:9: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:9: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:86:9: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:9: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
107 | ~IO(){clear();}
| ^
answer.code:107:9: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:9: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:107:9: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:23: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
108 | inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
| ^
answer.code:108:23: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:23: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:108:23: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:109:32: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
109 | inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
| ^
answer.code:109:32: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:109:32: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:109:32: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:110:20: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
110 | inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
| ^
answer.code:110:20: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:110:20: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:110:20: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:111:34: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
111 | inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}
| ^
answer.code:111:34: warning: bad option ‘-fstrict-overflow’ to attribute ‘op...