QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#250630 | #6391. Airplane | World_Creater | 0 | 46ms | 47224kb | C++14 | 2.3kb | 2023-11-13 14:34:06 | 2023-11-13 14:34:07 |
Judging History
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);
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
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 46ms
memory: 47224kb
input:
200000 199999 0 199 58 60 83 5 10 182 87 65 104 153 197 137 80 143 34 181 62 48 10 57 86 58 117 10 171 188 95 52 95 140 126 0 196 85 87 14 10 139 177 92 31 18 102 146 68 9 91 124 156 38 41 121 183 10 32 174 171 29 49 26 118 1 69 185 57 168 54 159 195 95 9 32 195 70 85 174 158 82 33 197 66 189 198 11...
output:
result:
wrong answer 1st lines differ - expected: '200378', found: ''
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 3ms
memory: 34356kb
input:
6 10 0 0 6 1 8 0 5 6 2 3 5 4 6 4 3 5 6 2 3 6 3 4 3 1 6 1
output:
result:
wrong answer 1st lines differ - expected: '1', found: ''
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%