QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250631 | #6392. Curtains | World_Creater | 0 | 0ms | 0kb | C++14 | 2.4kb | 2023-11-13 14:34:42 | 2023-11-13 14:34:42 |
answer
#include<bits/stdc++.h>
using namespace std;
struct node{
int mn,cnt,sec;
node operator +(const node &b) const
{
node t=*this;
if(t.mn==b.mn)
{
t.cnt+=b.cnt;
t.sec=min(t.sec,b.sec);
}
else if(t.mn>b.mn)
{
t.sec=min(t.mn,b.sec);
t.mn=b.mn;
t.sec=b.sec;
}
else if(t.mn<b.mn)
{
t.sec=min(t.sec,b.mn);
}
return t;
}
};
struct segtree{
node tree[2000005];
int tag[2000005];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define M(l,r) ((l+r)>>1)
void pushup(int p)
{
tree[p]=tree[lc(p)]+tree[rc(p)];
}
void maketag(int p,int k)
{
tree[p].mn=max(tree[p].mn,k);
tag[p]=max(tag[p],k);
}
void pushdown(int p)
{
maketag(lc(p),tag[p]);
maketag(rc(p),tag[p]);
tag[p]=0;
}
void build(int p,int l,int r)
{
if(l==r)
{
tree[p]={0,1,10000000};
return ;
}
int mid=M(l,r);
build(lc(p),l,mid);
build(rc(p),mid+1,r);
pushup(p);
}
void modify(int p,int l,int r,int L,int R,int k)
{
if(tree[p].mn>=k) return ;
if(L<=l&&r<=R&&tree[p].sec>k)
{
maketag(p,k);
return ;
}
pushdown(p);
int mid=M(l,r);
if(L<=mid) modify(lc(p),l,mid,L,R,k);
if(mid<R) modify(rc(p),mid+1,r,L,R,k);
pushup(p);
}
node query(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tree[p];
pushdown(p);
int mid=M(l,r);
if(L<=mid&&mid<R) return query(lc(p),l,mid,L,R)+query(rc(p),mid+1,r,L,R);
if(L<=mid) return query(lc(p),l,mid,L,R);
if(mid<R) return query(rc(p),mid+1,r,L,R);
}
}T;
int n,m,q,ans[500005];
vector<int> rid[500005],qid[500005];
pair<int,int> range[500005],qu[500005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("beaconator.in","r",stdin);
freopen("beaconator.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
range[i]={l,r};
rid[r].emplace_back(i);
}
T.build(1,1,n);
for(int i=1;i<=q;i++)
{
int l,r;
cin>>l>>r;
qu[i]={l,r};
qid[r].emplace_back(i);
}
for(int i=1;i<=n;i++)
{
for(auto j:rid[i])
{
auto [l,r]=range[j];
T.modify(1,1,n,l,r,l);
}
for(auto j:qid[i])
{
auto [l,r]=qu[j];
auto res=T.query(1,1,n,l,r);
// cerr<<l<<" "<<r<<" "<<res.mn<<" "<<res.cnt<<" "<<res.sec<<"\n";
if(res.mn>=l) ans[j]=1;
}
}
for(int i=1;i<=q;i++)
{
cout<<(ans[i]?"YES":"NO")<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
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:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Dangerous Syscalls
Test #32:
score: 0
Dangerous Syscalls
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%