Submission #677071

#	Time	Username	Problem	Language	Result	Execution time	Memory
677071		Do_you_copy	Event Hopping (BOI22_events)	C++17	100 / 100	214 ms	16100 KiB

events

//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 4e5 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n, q;
bool invalid[maxN];
pii e[maxN];
int lift[maxN][20];
vector <int> node;
int st[maxN * 4];

void update(int id, int i, int x, int l = 1, int r = node.size()){
    if (l == r){
        if (e[st[id]].fi > e[x].fi) st[id] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) update(id << 1, i, x, l, mid);
    else update(id << 1 | 1, i, x, mid + 1, r);
    if (e[st[id << 1]].fi < e[st[id << 1 | 1]].fi) st[id] = st[id << 1];
    else st[id] = st[id << 1 | 1];
}

int get(int id, int i, int j, int l = 1, int r = node.size()){
    if (i > r || l > j) return 0;
    if (i <= l && r <= j) return st[id];
    int mid = (l + r) >> 1;
    int x = get(id << 1, i, j, l, mid);
    int y = get(id << 1 | 1, i, j, mid + 1, r);
    if (e[x].fi < e[y].fi) return x;
    else return y;
}

void Init(){
    cin >> n >> q;
    for (int i = 1; i <= n; ++i){
        cin >> e[i].fi >> e[i].se;
        node.pb(e[i].fi);
        node.pb(e[i].se);
    }
    e[0].fi = INT_MAX;
    sort(node.begin(), node.end());
    node.resize(unique(node.begin(), node.end()) - node.begin());
    for (int i = 1; i <= n; ++i){
        e[i].fi = upper_bound(node.begin(), node.end(), e[i].fi) - node.begin();
        e[i].se = upper_bound(node.begin(), node.end(), e[i].se) - node.begin();
        update(1, e[i].se, i);
    }
    for (int i = 1; i <= n; ++i){
        int u = get(1, e[i].fi, e[i].se);
        if (e[u].fi == e[i].fi) continue;
        lift[i][0] = u;
    }
    for (int i = 1; i < 20; ++i){
        for (int j = 1; j <= n; ++j){
            lift[j][i] = lift[lift[j][i - 1]][i - 1];
        }
    }
    e[0].fi = 0;
    while (q--){
        int s, t;
        cin >> s >> t;
        if (s == t){
            cout << "0\n"; continue;
        }
        if (e[t].se < e[s].se){
            cout << "impossible\n"; continue;
        }
        if (e[t].fi <= e[s].se){
            cout << "1\n"; continue;
        }
        int ans = 0;
        for (int i = 19; i >= 0; --i){
            if (e[lift[t][i]].fi > e[s].se){
                t = lift[t][i];
                ans += 1 << i;
            }
        }
        t = lift[t][0];
        if (t == 0){
            cout << "impossible\n"; continue;
        }
        cout << ans + 2 << "\n";
    }
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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