Submission #645244

#	Time	Username	Problem	Language	Result	Execution time	Memory
645244		Vladth11	Event Hopping (BOI22_events)	C++14	100 / 100	200 ms	28536 KiB

events

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int bSize = 100001;
const int bits = 17;
const int NMAX = 100001;
const int VMAX = NMAX * 89;

int dp[NMAX][bits + 1];

pii aint[NMAX * 8];
unordered_map <int, int> mp;
pii v[NMAX];

bool cmp(pii a, pii b){
    if(a.second != b.second){
        return a.second > b.second;
    }
    return a.first > b.first;
}

void update(int node, int st, int dr, int a, pii p){
    if(st == dr){
        aint[node] = min(aint[node], p);
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid){
        update(node * 2, st, mid, a, p);
    }else{
        update(node * 2 + 1, mid + 1, dr, a, p);
    }
    aint[node] = min(aint[node * 2], aint[node * 2 + 1]);
}

pii query(int node, int st, int dr, int a, int b){
    if(a <= st && dr <= b){
        return aint[node];
    }
    int mid = (st + dr) / 2;
    pii maxim = {1e9, 1e9};
    if(a <= mid)
        maxim = min(maxim, query(node * 2, st, mid, a, b));
    if(b > mid)
        maxim = min(maxim, query(node * 2 + 1, mid + 1, dr, a, b));
    return maxim;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, i;
    cin >> n >> q;
    for(i = 0; i < NMAX * 8; i++){
        aint[i] = {1e9, 1e9};
    }
    vector <int> nrm;
    for(i = 1; i <= n; i++){
        cin >> v[i].first >> v[i].second;
        nrm.push_back(v[i].first);
        nrm.push_back(v[i].second);
    }
    int cnt = 0;
    sort(nrm.begin(), nrm.end());
    for(int i = 0; i < nrm.size(); i++){
        if(i == 0 || nrm[i] != nrm[i - 1])
            cnt++;
        mp[nrm[i]] = cnt;
    }
    for(i = 1; i <= n; i++){
        v[i].first = mp[v[i].first];
        v[i].second = mp[v[i].second];
    }
    for(i = 1; i <= n; i++){
        update(1, 1, 2 * n, v[i].second, {v[i].first, i});
    }
    for(i = 1; i <= n; i++){
        pii maxim = query(1, 1, 2 * n, v[i].first, v[i].second);
        dp[i][0] = maxim.second;
    }
    for(int j = 1; j <= bits; j++){
        for(int i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1]; /// Oare cand nu o sa mai uit sa fac stramosii
        }
    }
    while(q--){
        int x, y;
        cin >> x >> y;
        int node = y;
        int sol = 0;
        int pas = bits;
        while(pas >= 0){
            int nxt = dp[node][pas];
            if(nxt != 0 && v[nxt].first > v[x].second){
                node = nxt;
                sol += (1 << pas);
            }
            pas--;
        }
        if(v[node].first > v[x].second){
            node = dp[node][0];
            sol++;
        }
        if(v[node].first <= v[x].second && v[x].second <= v[node].second){
            cout << sol + (x != y) << "\n";
        }else{
            cout << "impossible\n";
        }
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < nrm.size(); i++){
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30