NOIP2023 游记
Y2hlbnlpa2Fp · · 个人记录
0.5h 切了前两题。
T3 花了 2.5h 写了 300+ 行。
来不及想 T4 了，写了
出来说 T4 比 T3 简单，人麻了。
回来测没挂，
SH 有好几个初中生阿克了。绷。
grg：SH 至少有
5 个 AK。
upd：似乎有
upd：官方数据
附 T3 考场代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define re(i,a,b) for(int i=a;i<b;i++)
char *p1,*p2,buf[1<<21];
#define getchar() (p1==p2&&(p1=buf,p2=buf+fread(buf,1,1<<21,stdin),p1==p2)?EOF:(*p1++))
template<typename T>
void read(T &r){
r=0;
char c=getchar();
bool f=0;
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=1,c=getchar();
while(c>='0'&&c<='9')r=r*10+c-48,c=getchar();
if(f)r=-r;
}
void _FILE(string s){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
const ll N=500003;
ll id,n,m,q,x[N],y[N],xo[N],yo[N],mx[N],posx[N],mn[N],posn[N];
bool vst1[N],vst2[N];
ll x2[N],y2[N],cnt1=0,cnt2=0;
ll pre1[N],nxt1[N],pre2[N],nxt2[N];
bool solve(){
if(x[1]<=y[1]||x[n]<=y[m])return 0;
cnt1=0,cnt2=0;
fill(vst1+1,vst1+n+1,0);
fill(vst2+1,vst2+m+1,0);
rep(i,1,n){
mx[i]=mx[i-1],posx[i]=posx[i-1];
if(x[i]>mx[i])mx[i]=x[i],posx[i]=i;
}
mn[0]=1000000007;
rep(i,1,n){
mn[i]=mn[i-1],posn[i]=posn[i-1];
if(x[i]<mn[i])mn[i]=x[i],posn[i]=i;
}
ll pxmx=posx[n],pxmn=posn[n];
vst1[pxmx]=1,vst1[pxmn]=1;
if(pxmx<pxmn){
ll o=pxmx;
bool t=1;
while(o>1){
if(t)o=posn[o-1];
else o=posx[o-1];
vst1[o]=1;
t=!t;
}
}
else{
ll o=pxmn;
bool t=0;
while(o>1){
if(t)o=posn[o-1];
else o=posx[o-1];
vst1[o]=1;
t=!t;
}
}
rep(i,1,m){
mx[i]=mx[i-1],posx[i]=posx[i-1];
if(y[i]>mx[i])mx[i]=y[i],posx[i]=i;
}
mn[0]=1000000007;
rep(i,1,m){
mn[i]=mn[i-1],posn[i]=posn[i-1];
if(y[i]<mn[i])mn[i]=y[i],posn[i]=i;
}
ll pymx=posx[m],pymn=posn[m];
vst2[pymx]=1,vst2[pymn]=1;
if(pymx<pymn){
ll o=pymx;
bool t=1;
while(o>1){
if(t)o=posn[o-1];
else o=posx[o-1];
vst2[o]=1;
t=!t;
}
}
else{
ll o=pymn;
bool t=0;
while(o>1){
if(t)o=posn[o-1];
else o=posx[o-1];
vst2[o]=1;
t=!t;
}
}
if(x[pxmx]<=y[pymx]||x[pxmn]<=y[pymn])return 0;
if(x[pxmx]==x[pxmn]||y[pymx]==y[pymn])return 1;
if((pxmn==1||pxmn==n)&&(pymx==1||pymx==m))return 1;
mx[n+1]=0,posx[n+1]=0;
per(i,n,1){
mx[i]=mx[i+1],posx[i]=posx[i+1];
if(x[i]>mx[i])mx[i]=x[i],posx[i]=i;
}
mn[n+1]=1000000007,posn[n+1]=0;
per(i,n,1){
mn[i]=mn[i+1],posn[i]=posn[i+1];
if(x[i]<mn[i])mn[i]=x[i],posn[i]=i;
}
if(pxmx<pxmn){
ll o=pxmn;
bool t=1;
while(o!=n){
if(t)o=posx[o+1];
else o=posn[o+1];
vst1[o]=1;
t=!t;
}
}
else{
ll o=pxmx;
bool t=0;
while(o!=n){
if(t)o=posx[o+1];
else o=posn[o+1];
vst1[o]=1;
t=!t;
}
}
mx[m+1]=0,posx[m+1]=0;
per(i,m,1){
mx[i]=mx[i+1],posx[i]=posx[i+1];
if(y[i]>mx[i])mx[i]=y[i],posx[i]=i;
}
mn[m+1]=1000000007,posn[m+1]=0;
per(i,m,1){
mn[i]=mn[i+1],posn[i]=posn[i+1];
if(y[i]<mn[i])mn[i]=y[i],posn[i]=i;
}
if(pymx<pymn){
ll o=pymn;
bool t=1;
while(o!=m){
if(t)o=posx[o+1];
else o=posn[o+1];
vst2[o]=1;
t=!t;
}
}
else{
ll o=pymx;
bool t=0;
while(o!=m){
if(t)o=posx[o+1];
else o=posn[o+1];
vst2[o]=1;
t=!t;
}
}
cnt1=0,cnt2=0;
rep(i,1,n){
if(vst1[i])x2[++cnt1]=x[i];
if(i==pxmx)pxmx=cnt1;
if(i==pxmn)pxmn=cnt1;
}
rep(i,1,m){
if(vst2[i])y2[++cnt2]=y[i];
if(i==pymx)pymx=cnt2;
if(i==pymn)pymn=cnt2;
}
x2[0]=0,x2[cnt1+1]=0;
y2[0]=0,y2[cnt2+1]=0;
ll tpos=pymn;
for(int i=pxmn;i>0;i-=2){
while(tpos>0&&y2[tpos]<x2[i])tpos-=2;
pre1[i]=tpos+2;
}
tpos=pymn;
for(int i=pxmn;i<=cnt1;i+=2){
while(tpos<=cnt2&&y2[tpos]<x2[i])tpos+=2;
nxt1[i]=tpos-2;
}
tpos=pxmx;
for(int i=pymx;i>0;i-=2){
while(tpos>0&&x2[tpos]>y2[i])tpos-=2;
pre2[i]=tpos+2;
}
tpos=pxmx;
for(int i=pymx;i<=cnt2;i+=2){
while(tpos<=cnt1&&x2[tpos]>y2[i])tpos+=2;
nxt2[i]=tpos-2;
}
// cout<<cnt1<<' '<<cnt2<<endl;
// rep(i,1,cnt1)cout<<x2[i]<<' ';cout<<endl;
// rep(i,1,cnt2)cout<<y2[i]<<' ';cout<<endl;
bool res=0;
if(pre2[pymx]<pxmn&&nxt1[pxmn]>pymx){
bool flag=1;
ll o=pymx,mn1=cnt1,mn2=pymx;
bool t=1;
while(1){
ll r=0;
if(t){
r=pre2[o];
if(r<mn1)mn1=r;
else{
flag=0;
break;
}
}
else{
r=pre1[o];
if(r<mn2)mn2=r;
else{
flag=0;
break;
}
}
if(r<=2)break;
o=r-1;
t=!t;
}
ll mx1=pxmn,mx2=0;
t=1;
o=pxmn;
while(1){
ll r=0;
if(t){
r=nxt1[o];
if(r>mx2)mx2=r;
else{
flag=0;
break;
}
}
else{
r=nxt2[o];
if(r>mx1)mx1=r;
else{
flag=0;
break;
}
}
if((t==1&&r>=cnt2-1)||(t==0&&r>=cnt1-1))break;
o=r+1;
t=!t;
}
res=res||flag;
}
if(nxt2[pymx]>pxmn&&pre1[pxmn]<pymx){
bool flag=1;
ll o=pxmn,mn1=pxmn,mn2=cnt2;
bool t=0;
while(1){
ll r=0;
if(t){
r=pre2[o];
if(r<mn1)mn1=r;
else{
flag=0;
break;
}
}
else{
r=pre1[o];
if(r<mn2)mn2=r;
else{
flag=0;
break;
}
}
if(r<=2)break;
o=r-1;
t=!t;
}
ll mx1=0,mx2=pymx;
t=0;
o=pymx;
while(1){
ll r=0;
if(t){
r=nxt1[o];
if(r>mx2)mx2=r;
else{
flag=0;
break;
}
}
else{
r=nxt2[o];
if(r>mx1)mx1=r;
else{
flag=0;
break;
}
}
if((t==1&&r>=cnt2-1)||(t==0&&r>=cnt1-1))break;
o=r+1;
t=!t;
}
res=res||flag;
}
return res;
}
bool Solve(){
bool res1=solve();
rep(i,1,max(n,m))swap(x[i],y[i]);
swap(n,m);
bool res2=solve();
rep(i,1,max(n,m))swap(x[i],y[i]);
swap(n,m);
return res1||res2;
}
int main(){
_FILE("expand");
read(id),read(n),read(m),read(q);
rep(i,1,n)read(x[i]),x[i]++;
rep(i,1,m)read(y[i]),y[i]++;
memcpy(xo+1,x+1,n*sizeof(ll));
memcpy(yo+1,y+1,m*sizeof(ll));
putchar(Solve()+'0');
rep(i,1,q){
memcpy(x+1,xo+1,n*sizeof(ll));
memcpy(y+1,yo+1,m*sizeof(ll));
ll k1,k2;
read(k1),read(k2);
rep(j,1,k1){
ll in1,in2;
read(in1),read(in2);
x[in1]=in2+1;
}
rep(j,1,k2){
ll in1,in2;
read(in1),read(in2);
y[in1]=in2+1;
}
putchar(Solve()+'0');
}
return 0;
}