Submission #1124398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124398		tuannm	Curtains (NOI23_curtains)	C++20	100 / 100	749 ms	59648 KiB

curtains

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 5e5 + 1;
const string NAME = "";
int n, m, q;
vector<int> lft[N];
vector<ii> queries[N];
bool ans[N];
int tree[4 * N], lazy[4 * N];

void down(int s){
    tree[2 * s] = max(tree[2 * s], lazy[s]);
    tree[2 * s + 1] = max(tree[2 * s + 1], lazy[s]);
    lazy[2 * s] = max(lazy[2 * s], lazy[s]);
    lazy[2 * s + 1] = max(lazy[2 * s + 1], lazy[s]);

    lazy[s] = 0;
}

void update(int s, int l, int r, int u, int v, int val){
    if(l > v || r < u)
        return;

    if(u <= l && r <= v){
        tree[s] = max(tree[s], val);
        lazy[s] = max(lazy[s], val);
        return;
    }

    down(s);
    int mid = l + r >> 1;

    update(2 * s, l, mid, u, v, val);
    update(2 * s + 1, mid + 1, r, u, v, val);

    tree[s] = min(tree[2 * s], tree[2 * s + 1]);
}

int get(int s, int l, int r, int u, int v){
    if(l > v || r < u)
        return 1e9;

    if(u <= l && r <= v)
        return tree[s];

    down(s);
    int mid = l + r >> 1;

    return min(get(2 * s, l, mid, u, v), get(2 * s + 1, mid + 1, r, u, v));
}

void inp(){
    cin >> n >> m >> q;

    for(int i = 1; i <= m; ++i){
        int l, r;
        cin >> l >> r;
        lft[r].pb(l);
    }

    for(int i = 1; i <= q; ++i){
        int s, t;
        cin >> s >> t;

        queries[t].pb({s, i});
    }
}

void solve(){

    for(int r = 1; r <= n; ++r){
        for(int l : lft[r])
            update(1, 1, n, l, r, l);

        for(auto [l, id] : queries[r])
            ans[id] = (get(1, 1, n, l, r) == l);
    }

    for(int i = 1; i <= q; ++i)
        cout << (ans[i] ? "YES\n" : "NO\n");
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message (stderr)

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