Submission #1009192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009192		User0069	Curtains (NOI23_curtains)	C++17	100 / 100	551 ms	53668 KiB

curtains

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e6+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,q,ST[maxn*4],laz[4*maxn],ans[maxn];
struct query
{
    int l,r,i,type;
};
vector<query> v;
bool operator <(query a,query b)
{
    if(a.r==b.r) return a.type<b.type;
    else return a.r<b.r;
}
//void down(int id)
//{
//    ST[id*2]
//}
void update(int id,int cl,int cr,int l,int r,int val)
{
    if(cl>r||cr<l) return;
    if(cl>=l&&cr<=r)
    {
        ST[id]=max(ST[id],val);
        return;
    }
    ST[id*2]=max(ST[id*2],ST[id]);
    ST[id*2+1]=max(ST[id*2+1],ST[id]);
    int mid=(cl+cr)/2;
    update(2*id,cl,mid,l,r,val);
    update(2*id+1,mid+1,cr,l,r,val);
    ST[id]=min(ST[id*2],ST[id*2+1]);
}
int get(int id,int cl,int cr,int l,int r)
{
    if(cr<l||cl>r) return n+1;
    if(cl>=l&&cr<=r) return ST[id];
    int mid=(cl+cr)/2;
    ST[id*2]=max(ST[id*2],ST[id]);
    ST[id*2+1]=max(ST[id*2+1],ST[id]);
    return min(get(2*id,cl,mid,l,r),get(2*id+1,mid+1,cr,l,r));
}
void solve()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        v.push_back({l,r,0,1});
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        v.push_back({l,r,i,2});
    }
    sort(v.begin(),v.end());
    for(query x:v)
    {
        if(x.type==1)
        {
           update(1,1,n,x.l,x.r,x.l);
        }
        else
        {
            ans[x.i]=get(1,1,n,x.l,x.r)>=x.l;
        }
    }
    for(int i=1;i<=q;i++)
    {
        cout<<(ans[i]?"YES\n":"NO\n");
    }
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    int t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20