oj.uz

Submission #921199

# Submission time Handle Problem Language Result Execution time Memory
921199 2024-02-03T13:29:57 Z WongYiKai Trampoline (info1cup20_trampoline) C++14
11 / 100
 856 ms 113740 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* Pre-computation using DFS */
const int MAXN = 600000;
const int LOGN = 20;
int p[LOGN+1][MAXN],h[MAXN];
vector<int> adjList[MAXN];
bitset<MAXN> visited;
void dfs(int x) {
    // cout << x << " ";
    if (visited[x]) return;
    visited[x] = 1;
    for (int k = 0; k < LOGN; ++k) {
        if (p[k][x] == -1) break;
        p[k+1][x] = p[k][p[k][x]];
    }
    for (auto it:adjList[x]) {
        if (visited[it]) continue;
        p[0][it] = x;
        h[it] = h[x]+1;
        dfs(it);
    }
}

/* Per query, d-th ancestor of x */
int ancestor(int x, int d) {
    for (int k = 0; k <= LOGN && x != -1; ++k) {
        if (d & (1<<k)) 
            x = p[k][x];
    }
    return x;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll r,c,n;
    cin >> r >> c >> n;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    vector<pair<ll,ll>> mem;
    map<ll,set<ll>> m;
    map<ll,ll> far;
    for (int i=0;i<n;i++){
        ll a,b;
        cin >> a >> b;
        pq.push({a,b});
        m[a].insert(b);
        far[a] = max(far[a],b);
    }
    queue<ll> q;
    ll prev=0;
    ll count=-1;
    map<pair<ll,ll>,ll> mem2;
    while (!pq.empty()){
        ll a=pq.top().first;
        ll b=pq.top().second;
        if (a!=prev){
            if (a!=prev+1){
                while (!q.empty()){
                    // cout << "a" << " ";
                    dfs(q.front());
                    q.pop();
                }
            }
            else {
                while (!q.empty() && mem[q.front()].first!=prev){
                    // cout << "b" << " ";
                    dfs(q.front());
                    q.pop();
                }
            }
        }
        mem.push_back({a,b});
        count++;
        mem2[{a,b}] = count;
        while (!q.empty() && mem[q.front()].second <= b){
            adjList[count].push_back(q.front());
            adjList[q.front()].push_back(count);
            q.pop();
        }
        q.push(count);
        prev=a;
        pq.pop();
    }
    while (!q.empty()){
        // cout << "c" << " ";
        dfs(q.front());
        q.pop();
    }
    // for (int i=0;i<n;i++) cout << h[i] << " ";
    ll t;
    cin >> t;
    for (int i=0;i<t;i++){
        ll x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1>x2) {
            cout << "No" << "\n";
            continue;
        }
        if (y2<y1){
            cout << "No" << "\n";
            continue;
        }
        if (x1==x2) {
            cout << "Yes" << "\n";
            continue;
        }
        auto vertex = m[x1].lower_bound(y1);
        if (y1 > far[x1]){
            cout << "No" << "\n";
            continue;
        }
        ll ind = mem2[{x1,*vertex}];
        ll dist = x2-x1-1;
        if (h[ind]<dist){
            cout << "No" << "\n";
            continue;
        }
        ll temp = ancestor(ind,dist);
        ll end = mem[temp].second;
        if (end <= y2) cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
// cout << ancestor(0,0);
}

Subtask #1
0 / 23.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 ms 100528 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 412 ms 95516 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 435 ms 95156 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 448 ms 100716 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 464 ms 100008 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 482 ms 100032 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 618 ms 110752 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 16 ms 58968 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 856 ms 113740 KB expected YES, found NO [15th token]
2 Halted 0 ms 0 KB -