oj.uz

Submission #1088716

# Submission time Handle Problem Language Result Execution time Memory
1088716 2024-09-14T21:40:00 Z vladilius Curtains (NOI23_curtains) C++17
24 / 100
 1500 ms 22136 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

struct ST{
    vector<int> a;
    int n;
    ST(int ns){
        n = ns;
        a.resize(n + 1);
    }
    void chmax(int l, int r, int x){
        for (int i = l; i <= r; i++){
            a[i] = max(a[i], x);
        }
    }
    int get(int l, int r){
        int mn = n + 1;
        for (int i = l; i <= r; i++){
            mn = min(mn, a[i]);
        }
        return mn;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> st[n + 1];
    while (m--){
        int l, r; cin>>l>>r;
        st[r].pb(l);
    }
    vector<pii> qs[n + 1];
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        qs[r].pb({l, i});
    }
    vector<int> out(q + 1);
    ST T(n);
    for (int r = 1; r <= n; r++){
        for (int l: st[r]){
            T.chmax(l, r, l);
        }
        for (auto [l, i]: qs[r]){
            out[i] = (T.get(l, r) >= l);
        }
    }
    
    for (int i = 1; i <= q; i++){
        cout<<(out[i] ? "YES" : "NO")<<"\n";
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 464 KB Output is correct
17 Correct 3 ms 564 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 464 KB Output is correct
17 Correct 3 ms 564 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 302 ms 14524 KB Output is correct
23 Correct 300 ms 14928 KB Output is correct
24 Correct 348 ms 16468 KB Output is correct
25 Correct 552 ms 22136 KB Output is correct
26 Correct 295 ms 14720 KB Output is correct
27 Correct 560 ms 22096 KB Output is correct
28 Correct 552 ms 22100 KB Output is correct
29 Correct 256 ms 13652 KB Output is correct
30 Correct 401 ms 13852 KB Output is correct
31 Correct 422 ms 14716 KB Output is correct
32 Correct 673 ms 21316 KB Output is correct
33 Correct 391 ms 13860 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 402 ms 13888 KB Output is correct
9 Correct 431 ms 14556 KB Output is correct
10 Correct 689 ms 21200 KB Output is correct
11 Correct 396 ms 13904 KB Output is correct
12 Execution timed out 1551 ms 12584 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 464 KB Output is correct
17 Correct 3 ms 564 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 479 ms 5712 KB Output is correct
23 Correct 468 ms 5716 KB Output is correct
24 Execution timed out 1549 ms 11860 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 464 KB Output is correct
17 Correct 3 ms 564 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 302 ms 14524 KB Output is correct
23 Correct 300 ms 14928 KB Output is correct
24 Correct 348 ms 16468 KB Output is correct
25 Correct 552 ms 22136 KB Output is correct
26 Correct 295 ms 14720 KB Output is correct
27 Correct 560 ms 22096 KB Output is correct
28 Correct 552 ms 22100 KB Output is correct
29 Correct 256 ms 13652 KB Output is correct
30 Correct 401 ms 13852 KB Output is correct
31 Correct 422 ms 14716 KB Output is correct
32 Correct 673 ms 21316 KB Output is correct
33 Correct 391 ms 13860 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 372 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 3 ms 692 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 402 ms 13888 KB Output is correct
42 Correct 431 ms 14556 KB Output is correct
43 Correct 689 ms 21200 KB Output is correct
44 Correct 396 ms 13904 KB Output is correct
45 Execution timed out 1551 ms 12584 KB Time limit exceeded
46 Halted 0 ms 0 KB -