oj.uz

Submission #893827

# Submission time Handle Problem Language Result Execution time Memory
893827 2023-12-27T14:10:19 Z kh0i Curtains (NOI23_curtains) C++17
9 / 100
 80 ms 47700 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e5 + 3;

int n, m, q;
pair<int, int> a[N], d[N];

namespace Sub12{
    bool valid_input(){ return n <= 2000 and m <= 2000 and q <= 2000; }
    void solve(){
        for(int i = 1; i <= q; ++i){
            vector<int> ck(n + 2, 0);
            for(int j = 1; j <= m; ++j){
                if(d[i].first <= a[j].first and a[j].second <= d[i].second)
                    ++ck[a[j].first], --ck[a[j].second + 1];
            }
            for(int j = 1; j <= n; ++j)
                ck[j] += ck[j - 1];
            bool ok = 1;
            for(int j = d[i].first; j <= d[i].second; ++j)
                ok &= (ck[j] > 0);
            cout << (ok ? "YES\n" : "NO\n");
        }
    }
}

namespace Sub3{
    bool valid_input(){ return n <= 2000; }

    bool has[2003][2003], ok[2003][2003];
    int p[2003][2003];

    void solve(){
        for(int i = 1; i <= n; ++i){
            has[a[i].first][a[i].second] = 1;
            p[a[i].first][a[i].second] = 1;
        }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                p[j][i] += p[j - 1][i];
        for(int i = 1; i <= n; ++i){
            int cur = i - 1;
            for(int j = i; j <= n; ++j){
                if(has[i][j])
                    ok[i][j] = 1;
                else
                    ok[i][j] = (cur >= i ? p[cur + 1][j] - p[i - 1][j] : 0);
                cur = (ok[i][j] ? j : cur);
            }
        }
        for(int i = 1; i <= q; ++i)
            cout << (ok[d[i].first][d[i].second] ? "YES\n" : "NO\n");
    }
}

namespace Sub4{
    bool valid_input(){
        bool ok = 1;
        for(int i = 1; i <= q; ++i)
            ok &= (d[i].first == 1);
        return ok;
    }

    bool has[N], f[N];
    vector<int> rv[N];

    void solve(){
        for(int i = 1; i <= m; ++i){
            if(a[i].first == 1)
                has[a[i].second] = 1;
            rv[a[i].second].push_back(i);
        }
        int cur = 0;
        for(int i = 1; i <= n; ++i){
            if(has[i])
                f[i] = 1;
            else{
                for(int x : rv[i])
                    f[i] |= (a[x].first <= cur);
            }
            if(f[i])
                cur = i + 1;
        }
        for(int i = 1; i <= q; ++i)
            cout << (f[d[i].second] ? "YES\n" : "NO\n");
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i)
        cin >> a[i].first >> a[i].second;
    for(int i = 1; i <= q; ++i)
        cin >> d[i].first >> d[i].second;

    if(Sub12::valid_input())
        Sub12::solve();
    else if(Sub3::valid_input())
        Sub3::solve();
    else if(Sub4::valid_input())
        Sub4::solve();


    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 17052 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17040 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 17240 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 17052 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17040 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 17240 KB Output is correct
13 Correct 31 ms 16988 KB Output is correct
14 Correct 29 ms 17108 KB Output is correct
15 Correct 29 ms 16988 KB Output is correct
16 Correct 29 ms 17084 KB Output is correct
17 Correct 28 ms 17244 KB Output is correct
18 Correct 24 ms 16988 KB Output is correct
19 Correct 24 ms 16988 KB Output is correct
20 Correct 27 ms 16988 KB Output is correct
21 Correct 28 ms 16988 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 17052 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17040 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 17240 KB Output is correct
13 Correct 31 ms 16988 KB Output is correct
14 Correct 29 ms 17108 KB Output is correct
15 Correct 29 ms 16988 KB Output is correct
16 Correct 29 ms 17084 KB Output is correct
17 Correct 28 ms 17244 KB Output is correct
18 Correct 24 ms 16988 KB Output is correct
19 Correct 24 ms 16988 KB Output is correct
20 Correct 27 ms 16988 KB Output is correct
21 Correct 28 ms 16988 KB Output is correct
22 Correct 78 ms 47400 KB Output is correct
23 Incorrect 80 ms 47700 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 17012 KB Output is correct
5 Correct 24 ms 16984 KB Output is correct
6 Correct 26 ms 16988 KB Output is correct
7 Correct 26 ms 16988 KB Output is correct
8 Incorrect 74 ms 46644 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 17052 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17040 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 17240 KB Output is correct
13 Correct 31 ms 16988 KB Output is correct
14 Correct 29 ms 17108 KB Output is correct
15 Correct 29 ms 16988 KB Output is correct
16 Correct 29 ms 17084 KB Output is correct
17 Correct 28 ms 17244 KB Output is correct
18 Correct 24 ms 16988 KB Output is correct
19 Correct 24 ms 16988 KB Output is correct
20 Correct 27 ms 16988 KB Output is correct
21 Correct 28 ms 16988 KB Output is correct
22 Incorrect 24 ms 18780 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 5 ms 17052 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 17040 KB Output is correct
9 Correct 3 ms 16984 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 4 ms 17240 KB Output is correct
13 Correct 31 ms 16988 KB Output is correct
14 Correct 29 ms 17108 KB Output is correct
15 Correct 29 ms 16988 KB Output is correct
16 Correct 29 ms 17084 KB Output is correct
17 Correct 28 ms 17244 KB Output is correct
18 Correct 24 ms 16988 KB Output is correct
19 Correct 24 ms 16988 KB Output is correct
20 Correct 27 ms 16988 KB Output is correct
21 Correct 28 ms 16988 KB Output is correct
22 Correct 78 ms 47400 KB Output is correct
23 Incorrect 80 ms 47700 KB Output isn't correct
24 Halted 0 ms 0 KB -