oj.uz

Submission #493829

# Submission time Handle Problem Language Result Execution time Memory
493829 2021-12-13T05:21:57 Z SirCovidThe19th Trampoline (info1cup20_trampoline) C++17
11 / 100
 1182 ms 51580 KB 
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)

const int mx = 2e5 + 5, ml = 18;

int R, C, n, q, col[mx], down[mx][ml]; map<int, set<pair<int, int>>> mp; 

int main(){
    cin >> R >> C >> n;
    FOR(i, 1, n + 1){
        int r, c; cin >> r >> c;
        col[i] = c;
        mp[r].insert({c, i});
    }
    for (auto [r, S] : mp)
        for (auto [c, idx] : S){
            auto it = mp[c + 1].lower_bound({r, -1});
            if (it != mp[c + 1].end()) down[idx][0] = it->second;
        }
    FOR(l, 1, ml) FOR(i, 1, n + 1) down[i][l] = down[down[i][l - 1]][l - 1];

    cin >> q;
    while (q--){
        int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
        if (r1 > r2 or c1 > c2){ cout<<"No"<<"\n"; continue; }
        if (r1 == r2){ cout<<"Yes"<<"\n"; continue; }

        auto st = mp[r1].lower_bound({c1, -1});
        int cur = (st == mp[r1].end()) ? 0 : st->second;
        int jmp = r2 - r1 - 1;

        FOR(l, 0, ml) if ((jmp >> l) & 1) cur = down[cur][l];
        cout<<((!cur or col[cur] > c2) ? "No" : "Yes")<<"\n";
    }
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1360 KB expected NO, found YES [7th token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 25068 KB expected YES, found NO [3rd token]
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1125 ms 45808 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 1182 ms 44280 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 1077 ms 44276 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 1096 ms 44464 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 1111 ms 44376 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 1081 ms 50488 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1288 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1148 ms 51580 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -