Submission #599097

#	Time	Username	Problem	Language	Result	Execution time	Memory
599097		MadokaMagicaFan	Event Hopping (BOI22_events)	C++14	100 / 100	395 ms	29852 KiB

events

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define forn(i,n)       for(int i = 0; i < n; ++i)
#define forr(i,n)       for(int i = n-1; i >= 0; --i)
#define forbe(i,b,e)    for(int i = b; i < e; ++i)

#define all(v)          (v).begin(),(v).end()
#define sort(v)         sort(all(v))
#define sz(v)           ((int)(v).size())

#define pb              push_back

#define endl            '\n'

const int K = 18;

using ai = array<int,2>;
using aii = array<int,3>;

struct aint {
    ai nm;
    int n;
    vector<ai> f;

    aint(int _n, ai _nm) :
        n(_n), nm(_nm)
    {
        f.assign(4*n, nm);
    }

    void upd(int i, int l, int r, int e, int s, int ind) {
        int mid = (l+r)>>1;
        if (e < l || r < e) return;
        if (l == r) {
            if (f[i][0] > s) {
                f[i][0] = s;
                f[i][1] = ind;
            }
            return;
        }

        upd(i<<1, l, mid, e, s , ind);
        upd(i<<1|1, mid+1, r, e, s , ind);

        ai al = f[i<<1];
        ai ar = f[i<<1|1];

        f[i] = al;

        if (al[0] > ar[0]) f[i] = ar;
    }

    ai query(int i, int l, int r, int tl, int tr) {
        int mid = (l+r)>>1;
        if (tr < l || r < tl) return nm;
        if (tl <= l && r <= tr) return f[i];

        
        ai al = query(i<<1, l, mid, tl, tr);
        ai ar = query(i<<1|1, mid+1, r, tl, tr);
        
        if (al[0] > ar[0]) return ar;
        return al;
    }

    void upd(int s, int e, int i) { upd(1, 0, n-1, e, s, i); }

    ai query(int l, int r) { return query(1, 0, n-1, l, r); }
};


void
solve() {
    int n, q;
    cin >> n >> q;

    vi s(n), e(n);

    forn(i,n)
        cin >> s[i] >> e[i];
    
    vi norm;
    map<int, int> normap;
    forn(i,n) norm.pb(s[i]);
    forn(i,n) norm.pb(e[i]);

    sort(norm);
    norm.resize(distance(norm.begin(), unique(all(norm))));
    forn(i, sz(norm)) normap[norm[i]] = i;

    forn(i,n) s[i] = normap[s[i]];
    forn(i,n) e[i] = normap[e[i]];

    aint tr(sz(norm), {sz(norm)+5,-1});
    forn(i, n) tr.upd(s[i], e[i], i);

    vector<array<int,K>> p(n);
    forn(i, n) p[i][0] = i;

    forn(i, n) {
        ai qv = tr.query(s[i], e[i]);
        p[i][0] = qv[1];
    }

    forbe(j, 1, K) {
        forn(i, n) {
            p[i][j] = p[p[i][j-1]][j-1];
        }
    }
//    return;
//
//
//    set<int> cords;
//    vector<pi> qu;
//
//    forn(i, n) { qu.pb({s[i], e[i]}); }
//    sort(qu);
//
//    int pnt = 0;
//
    vector<ai> qs(q);
    vi ans(q);

    forn(i, q) cin >> qs[i][0] >> qs[i][1];
    forn(i, q) --qs[i][0];
    forn(i, q) --qs[i][1];


//    priority_queue<ai> pq;
    forn(i, q) {
        if (qs[i][0] == qs[i][1]) {
            ans[i] = 0;
            continue;
        }

        if (e[qs[i][0]] > e[qs[i][1]]) {
            ans[i] = -1;
            continue;
        }

        if (e[qs[i][0]] >= s[qs[i][1]]) {
            ans[i] = 1;
            continue;
        }
        
        int st = qs[i][0];
        int en = qs[i][1];

//        cout << "Query " << i << ": " << st << ' ' << en << endl;

        int tans = 0;

        forr(j, K) {
            if (s[p[en][j]] > e[st]) {
                tans += (1<<j);
                en = p[en][j];
            }
        }

        if (s[p[en][0]] > e[st]) {
            ans[i] = -1;
            continue;
        }

        ans[i] = tans+2;
    }

    forn(i, q) {
        if (ans[i] == -1)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

int32_t
main(int argc, char** argv) {
    if (argc > 1)
        freopen(argv[1],"r", stdin);
    solve();
}

Compilation message (stderr)

events.cpp: In constructor 'aint::aint(int, ai)':
events.cpp:28:9: warning: 'aint::n' will be initialized after [-Wreorder]
   28 |     int n;
      |         ^
events.cpp:27:8: warning:   'ai aint::nm' [-Wreorder]
   27 |     ai nm;
      |        ^~
events.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     aint(int _n, ai _nm) :
      |     ^~~~
events.cpp: In function 'int32_t main(int, char**)':
events.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(argv[1],"r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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