Submission #933219

#	Time	Username	Problem	Language	Result	Execution time	Memory
933219		browntoad	Curtains (NOI23_curtains)	C++14	100 / 100	939 ms	61040 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

const ll maxn = 5e5+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;

vector<int> seg(4*maxn), tag(4*maxn);
void push(int x, int l, int r){
    seg[x] = max(seg[x], tag[x]);
    if (l < r){
        tag[x+x] = max(tag[x], tag[x+x]);
        tag[x+x+1] = max(tag[x], tag[x+x+1]);
    }
    tag[x] = 0;
}
int query(int l, int r, int nl, int nr, int x){
    push(x, nl, nr);
    if (l > nr || r < nl) return inf;
    if (l <= nl && nr <= r) return seg[x];
    int mid = nl+nr>>1;
    return min(query(l, r, nl, mid, x+x), query(l, r, mid+1, nr, x+x+1));
}
void modify(int l, int r, int nl, int nr, int v, int x){
    if (l > nr || r < nl){
        push(x, nl, nr);
        return;
    }
    if (l <= nl && nr <= r){
        tag[x] = max(tag[x], v);
        push(x, nl, nr);
        return;
    }
    push(x, nl, nr);
    int mid = nl+nr>>1;
    modify(l, r, nl, mid, v, x+x);
    modify(l, r, mid+1, nr, v, x+x+1);
    seg[x] = min(seg[x+x], seg[x+x+1]);
}
int n, m, q;
bool cmp(pip a, pip b){
    return a.s.s < b.s.s;
}
signed main(){
    IOS();
    cin>>n>>m>>q;
    vector<pip> mo(m), quer(q);
    vector<int> ans(q);
    REP(i, m){
        cin>>mo[i].s.f>>mo[i].s.s;
        mo[i].f = i;
    }
    REP(i, q){
        cin>>quer[i].s.f>>quer[i].s.s;
        quer[i].f = i;
    }
    sort(ALL(mo), cmp); sort(ALL(quer), cmp);

    int ptr = 0;
    REP(i, q){
        while(ptr < m && mo[ptr].s.s <= quer[i].s.s){
            modify(mo[ptr].s.f, mo[ptr].s.s, 1, n, mo[ptr].s.f, 1);
            ptr++;
        }
        if (query(quer[i].s.f, quer[i].s.s, 1, n, 1) >= quer[i].s.f){
            ans[quer[i].f] = 1;
        }
        else ans[quer[i].f] = 0;
    }
    REP(i, q) cout<<(ans[i]?"YES":"NO")<<endl;


}

Compilation message (stderr)

curtains.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = nl+nr>>1;
      |               ~~^~~
curtains.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = nl+nr>>1;
      |               ~~^~~

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