Submission #1102859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102859		spycoderyt	Curtains (NOI23_curtains)	C++17	0 / 100	675 ms	258764 KiB

curtains

#include <bits/stdc++.h>
#define pii pair<int,int> 
#define f first
#define s second
using namespace std;
const int N = 3e5+5;
struct tree{
    struct node{
        node *l,*r;
        int sum;
        node(int k) : sum(k),l(nullptr),r(nullptr) {}
        node(node* l,node* r) : l(l),r(r) {
            sum = max((l?l->sum:0),(r?r->sum:0));
        }
    };
    public:
    typedef node* pnode;
    pnode roots[N];
    node* build(int l,int r) {
        if(l==r)return new node(0);
        int mid = (l+r)/2;
        return new node(build(l,mid),build(mid+1,r));
    }
    node* upd(node* cur,int l,int r,int tar,int val) {
        if(l>r)return 0;
        if(l==r) return new node(val);
        assert(cur);
        int mid = (l+r)/2;
        if(tar > mid) return new node(cur->l,upd(cur->r,mid+1,r,tar,val));
        else return new node(upd(cur->l,l,mid,tar,val),cur->r);
    }
    int qry(node*cur,int l,int r,int ll,int rr) {
        if(l>r||r<ll|l>rr)return 0;
        if(l>=ll&&r<=rr)return cur->sum;
        int mid = (l+r)/2;
        return max(qry(cur->l,l,mid,ll,rr), qry(cur->r,mid+1,r,ll,rr));
    }
}t;
int n,m,q,a,b;
map<int,int> times;
int main() {
    cin>>n>>m>>q;
    vector<pii> v(m);
    vector<int> mx(n+1);
    vector<pii> qv(q);
    for(int i = 0;i<m;i++) {
        cin>>v[i].s>>v[i].f; // r, l
    }
    for(int i = 0;i<q;i++)cin>>qv[i].f>>qv[i].s;
    t.roots[0] = t.build(1,n);
    sort(v.begin(),v.end());
    for(int i = 0;i<m;i++) {
        times[v[i].f] = i+1;
        // cout << v[i].f << "awvdwa\n";
        mx[v[i].s] = max(mx[v[i].s],v[i].f);
        t.roots[i+1] = t.upd(t.roots[i],1,n,v[i].s,mx[v[i].s]+1);
    }
    for(int i = 0;i<q;i++) {
        // cout << qv[i].f << " " << qv[i].s << "wadwadwa\n";
        int can = 1;
        int time = times[qv[i].s];
        if(time ==0){
            cout << "NO\n";
            continue;
        }
        if(qv[i].f == qv[i].s) {
            if(t.qry(t.roots[time],1,n,qv[i].f,qv[i].f) == qv[i].f) cout << "YES\n";
            else cout << "NO\n";
            continue;
        }
        //search from .s to .f, see if max is equal to .f
        int l = qv[i].f, r = qv[i].f;
        // cout << l << " " << r << " " << time << "\n";
        while(r < qv[i].s) {
            int oldr = r;
            r = t.qry(t.roots[time],1,n,l,r);
            // cout << r << "\n";
            if(r <= oldr) {
                can = 0;
                break;
            }
        }
        if(can)cout<<"YES\n";
        else cout << "NO\n";
    }
    
}

/*
6 3 3
1 2
3 4
5 6
1 6
1 4
2 4

10 10 10
6 9
6 7
1 6
10 10
5 9
3 9
2 10
5 7
9 10
5 10

7 8
4 7
1 6
2 7
3 9
7 7
2 9
4 9
6 6
5 7

*/

Compilation message (stderr)

curtains.cpp: In constructor 'tree::node::node(int)':
curtains.cpp:10:13: warning: 'tree::node::sum' will be initialized after [-Wreorder]
   10 |         int sum;
      |             ^~~
curtains.cpp:9:15: warning:   'tree::node* tree::node::l' [-Wreorder]
    9 |         node *l,*r;
      |               ^
curtains.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         node(int k) : sum(k),l(nullptr),r(nullptr) {}
      |         ^~~~
curtains.cpp: In member function 'int tree::qry(tree::node*, int, int, int, int)':
curtains.cpp:33:18: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   33 |         if(l>r||r<ll|l>rr)return 0;
      |                 ~^~~

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