| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1345202 | kuzma_a | Curtains (NOI23_curtains) | C++20 | 1079 ms | 260116 KiB |
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int mv[30][500000],ch[30][500000];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,qq;
cin>>n>>m>>qq;
set<int>rt[n],lft[n];
set<int>crs;
for(int i = 0;i<m;i++){
int l,r;
cin>>l>>r;
l--;
r--;
if(l == r){
crs.insert(l);
}
rt[l].insert(r);
lft[r].insert(l);
}
set<int>qr[n];
map<pair<int,int>,int>mp;
vector<pair<int,int>>v1;
while(qq--){
int l,r;
cin>>l>>r;
l--;
r--;
v1.push_back(make_pair(l,r));
if(l < r){
qr[l].insert(r);
}
else if(crs.find(l) != crs.end()){
mp[make_pair(l,l)] = 1;
}
}
queue<pair<int,pair<int,int>>>q;
q.push(make_pair(0,make_pair(0,n-1)));
while(q.size()){
int l = q.front().second.first,r = q.front().second.second;
int k = q.front().first;
q.pop();
int m = (l+r)/2;
//cout<<l<<' '<<r<<endl;
for(int i = m;i>=l;i--){
mv[k][i] = n+2;
ch[k][i] = i;
int rr = i;
while(rt[i].size() && *--rt[i].end() > m){
mv[k][i] = *--rt[i].end();
rt[i].erase(--rt[i].end());
}
int go = i-1;
if(rt[i].size()){
go = *--rt[i].end();
}
if(go != m){
while(rr <= go+1){
if(rr > m){
break;
}
mv[k][i] = min(mv[k][i],mv[k][rr]);
rr = max(rr,ch[k][rr]);
if(rr <= go){
rr++;
}
else{
if(rr > m || ch[k][rr] <= rr){
if(rr <= m){
mv[k][i] = min(mv[k][i],mv[k][rr]);
}
break;
}
}
}
ch[k][i] = rr-1;
}
else{
mv[k][i] = m;
ch[k][i] = m;
}
}
for(int i = m+1;i<=r;i++){
mv[k][i] = -2;
ch[k][i] = i;
int ll = i;
while(lft[i].size() && *lft[i].begin() <= m){
mv[k][i] = *lft[i].begin();
lft[i].erase(lft[i].begin());
}
int go = i+1;
if(lft[i].size()){
go = *lft[i].begin();
}
if(go != m+1){
while(ll >= go-1){
if(ll <= m){
break;
}
mv[k][i] = max(mv[k][i],mv[k][ll]);
ll = min(ll,ch[k][ll]);
if(ll >= go){
ll--;
}
else{
if(ll <= m || ch[k][ll] >= ll){
if(ll > m){
mv[k][i] = max(mv[k][i],mv[k][ll]);
}
break;
}
}
}
ch[k][i] = ll+1;
}
else{
mv[k][i] = m+1;
ch[k][i] = m+1;
}
}
for(int i = l;i<=m;i++){
while(qr[i].size() && *--qr[i].end() > m){
int r = *--qr[i].end();
if(mv[k][r] >= i && mv[k][i] <= r){
mp[make_pair(i,r)] = 1;
}
//cout<<i<<' '<<r<<' '<<mp[make_pair(i,r)]<<endl;
qr[i].erase(--qr[i].end());
}
}
/*
for(int i = 0;i<n;i++){
cout<<mv[k][i]<<' ';
}
cout<<endl;
for(int i = 0;i<n;i++){
cout<<ch[k][i]<<' ';
}
cout<<endl;
*/
if(m > l){
q.push(make_pair(k+1,make_pair(l,m)));
}
if(m+1 < r){
q.push(make_pair(k+1,make_pair(m+1,r)));
}
}
for(auto it:v1){
if(mp[it]){
cout<<"YES";
}
else{
cout<<"NO";
}
cout<<"\n";
}
}| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
