Submission #1169036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169036		son2008	Curtains (NOI23_curtains)	C++20	100 / 100	739 ms	45708 KiB

curtains

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e5+1;
const int mod=1e9+7;
int n,m,q,ans[maxn],tree[4*maxn],lazy[4*maxn];
vector<ii>qe[maxn];
void down(int id)
{
    lazy[id*2]=max(lazy[id*2],lazy[id]);
    lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
    tree[id*2]=max(tree[id*2],lazy[id]);
    tree[id*2+1]=max(tree[id*2+1],lazy[id]);
    lazy[id]=0;
}
void update(int u,int v,int val,int id=1,int l=1,int r=n)
{
    if(u>r||v<l)return;
    if(u<=l&&v>=r)
    {
        tree[id]=max(tree[id],val);
        lazy[id]=max(lazy[id],val);
        return;
    }
    int mid=(l+r)/2;
    down(id);
    update(u,v,val,id*2,l,mid);
    update(u,v,val,id*2+1,mid+1,r);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}
int get(int u,int v,int id=1,int l=1,int r=n)
{
    if(u>r||v<l)return n+1;
    if(u<=l&&v>=r)
    {
        return tree[id];
    }
    int mid=(l+r)/2;
    down(id);
    return min(get(u,v,id*2,l,mid),get(u,v,id*2+1,mid+1,r));
}
void init()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        qe[r].push_back({l,-1});
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        qe[r].push_back({l,i});
    }
}
void process()
{
    for(int i=1;i<=n;i++)
    {
        for(ii x:qe[i])
        {
            if(x.se==-1)
            update(x.fi,i,x.fi);
            else
            {
                ans[x.se]=get(x.fi,i)>=x.fi;
            }
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(ans[i])cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

curtains.cpp: In function 'int main()':
curtains.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(task".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