QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883342 | #6392. Curtains | xiangqizhen | 0 | 128ms | 124876kb | C++14 | 4.5kb | 2025-02-05 15:57:33 | 2025-02-05 15:57:46 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#define f(i,j,n) for(int i=j;i<=n;i++)
#define F(i,n,j) for(int i=n;i>=j;i--)
#define updmax(a,b) a=max(a,b)
#define updmin(a,b) a=min(a,b)
#define pb push_back
#define XQZ
using namespace std;
namespace fsd{
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
const int MAXSIZE=1<<20;
char buf[MAXSIZE],*p1,*p2;
inline int read(){
int ak=0,ioi=1;char c=gc();
while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
while(isdigit(c))ak=ak*10+(c^48),c=gc();
return ak*ioi;
}
inline string reads(){
string o="";
char p=gc();
while(p>'z'||p<'a'){p=gc();}
while(p<='z'&&p>='a'){o+=p;p=gc();}
return o;
}
inline char readc(){
char p=gc();
while(!((p<='z'&&p>='a')||(p<='Z'&&p>='A'))){p=gc();}
return p;
}
inline long double readd(){
long double ak=0;int ioi=1;char c=gc();
while(!isdigit(c)){if(c=='-')ioi=-1;c=gc();}
while(isdigit(c))ak*=10,ak+=c-'0',c=gc();
c=gc();
long double q=0.1;
while(isdigit(c))ak+=(c-'0')*q,q*=0.1,c=gc();
return ak*ioi;
}
}
using namespace fsd;
const int inf=INT_MAX/2;
const int N=5e5+10;
struct Mst{
struct M{
int minn=inf,cminn=inf;
M& operator *=(int x){
if(minn>x){
cminn=minn,minn=x;
}else if(cminn>x&&x!=minn)cminn=x;
return *this;
}
friend M operator *(M x,M y){
x*=y.minn,x*=y.cminn;
return x;
}
M& operator *=(M x){
*this=*this*x;
return *this;
}
};
struct abc{int l,r,sum,tg,to;M minn;}Tree[N*8];
inline void build(int k,int l,int r){
Tree[k].l=l,Tree[k].r=r;Tree[k].tg=0;
if(l==r){return;}int mid=(l+r)>>1;build(k*2,l,mid);build(k*2+1,mid+1,r);
pushup(k);
/**/
}
inline void upd(int k,int v,int to){
if(Tree[k].minn.minn!=v)return;
Tree[k].minn.minn=to;
Tree[k].tg=v;
Tree[k].to=to;
/**/
}
inline void pushdown(int k){
if(Tree[k].tg){upd(k*2,Tree[k].tg,Tree[k].to);upd(k*2+1,Tree[k].tg,Tree[k].to);Tree[k].tg=0;}
/**/
}
inline void pushup(int k){
Tree[k].minn=Tree[k*2].minn*Tree[k*2+1].minn;Tree[k].sum=Tree[k*2].sum+Tree[k*2+1].sum;
/**/
}
inline void modify(int k,int l,int r,int L,int R){
// cout<<Tree[k].l<<" "<<Tree[k].r<<" "<<L<<" "<<R<<endl;
// cout<<Tree[k].minn.minn<<" "<<Tree[k].minn.cminn<<endl;
if(Tree[k].l>=l&&Tree[k].r<=r){
if(Tree[k].minn.minn>R)return;
if(Tree[k].minn.minn<=R&&Tree[k].minn.cminn>R){
if(!Tree[k].tg)Tree[k].tg=Tree[k].minn.minn;
Tree[k].minn.minn=L;
Tree[k].to=L;
return;
}
}
int mid=(Tree[k].l+Tree[k].r)>>1;
pushdown(k);
if(l<=mid)modify(k*2,l,r,L,R);
if(r>mid)modify(k*2+1,l,r,L,R);
pushup(k);
}
inline void modify(int k,int p,int v){
if(Tree[k].l==Tree[k].r){
Tree[k].minn.minn=v;
return;
}
int mid=(Tree[k].l+Tree[k].r)>>1;
pushdown(k);
if(p<=mid)modify(k*2,p,v);
else modify(k*2+1,p,v);
pushup(k);
}
int ask(int k,int L,int R){
if(L>R)return inf;
if(Tree[k].l>=L&&Tree[k].r<=R)return Tree[k].minn.minn;
pushdown(k);
int mid=(Tree[k].l+Tree[k].r)>>1;
int mm=inf;
if(L<=mid)updmin(mm,ask(k*2,L,R));
if(R>mid)updmin(mm,ask(k*2+1,L,R));
return mm;
}
}_mst;
int n,m;
struct abc{int l,r,i,I;}x[N];
int R[N];
struct as{
int l,r,i;
}ak[N];
int ans[N];
inline void gs(){
n=read();
m=read();
int q=read();
_mst.build(1,1,m);
f(i,1,m)x[i].l=read(),x[i].r=read()+1;
int FFF=x[1].l;
sort(x+1,x+1+m,[&](abc a,abc b){return a.r<b.r||(a.r==b.r&&a.l<b.l);});
f(i,1,m)x[i].i=i,R[i]=x[i].r;
f(i,1,m)if(x[i].r==x[i-1].r)x[i].I=x[i-1].I;else x[i].I=i;
f(i,1,q){
int l=read(),r=read();
ak[i]={l,r,i};
}
sort(ak+1,ak+1+q,[&](as a,as b){
return a.l>b.l;
});
sort(x+1,x+1+m,[&](abc a,abc b){return a.l>b.l;});
int j=1;
f(i,1,q){
// cout<<"=============="<<i<<"=============\n";
int l=ak[i].l,r=ak[i].r;
// if(FFF==56780||FFF==18975)continue;
while(j<=m&&x[j].l>=l)_mst.modify(1,x[j].I,m,x[j].l,x[j].r),_mst.modify(1,x[j].i,x[j].l),j++;
int t=upper_bound(R+1,R+1+m,r+1)-R-1;
int s=lower_bound(R+1,R+1+m,r+1)-R;
// cout<<ak[i].i<<":"<<l<<" "<<r<<" "<<s<<endl;
// cout<<_mst.ask(1,l,s)<<endl;
ans[ak[i].i]=(_mst.ask(1,s,t)<=l);
}
f(i,1,q)printf(ans[i]?"YES\n":"NO\n");
}
signed main(){
#ifndef XQZ
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef NXD
int t=0;cin>>t;while(t--)
#endif
gs();
return 0;
}
/*
10 10 10
6 9
6 7
1 6
10 10
5 9
3 9
2 10
5 7
9 10
5 10
7 8
4 7
1 6
2 7
3 9
7 7
2 9
4 9
6 6
5 7
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 120396kb
input:
200 200 200 113 134 77 77 110 143 126 157 122 131 161 172 59 134 19 68 117 142 15 103 61 182 12 67 73 97 72 128 68 110 19 137 14 118 60 150 42 64 25 30 118 158 149 164 79 149 21 94 33 82 3 130 36 142 57 170 64 140 40 98 115 132 2 45 27 85 43 181 120 125 82 160 121 176 16 154 59 74 34 52 71 74 57 185...
output:
NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO N...
result:
wrong answer 5th lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 128ms
memory: 124876kb
input:
100000 100000 100000 44237 85021 45776 80409 39632 94735 28119 63770 47399 73347 28902 87358 27924 65499 23898 54817 50114 96633 11325 37690 46642 94643 9271 47594 47324 47948 27957 58134 20443 88720 20834 89483 77577 94705 7835 30030 37387 59648 8364 76478 66145 76025 12683 79475 1745 33181 43966 5...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%