oj.uz

Submission #599071

# Submission time Handle Problem Language Result Execution time Memory
599071 2022-07-19T09:52:40 Z MadokaMagicaFan Event Hopping (BOI22_events) C++14
20 / 100
 421 ms 26800 KB 
#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];

        int tans = 0;

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

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

        ans[i] = tans+1;
    }

    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

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:183:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         freopen(argv[1],"r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 272 ms 18424 KB Output is correct
3 Correct 300 ms 18512 KB Output is correct
4 Correct 292 ms 18492 KB Output is correct
5 Correct 292 ms 19324 KB Output is correct
6 Correct 305 ms 20032 KB Output is correct
7 Correct 276 ms 20280 KB Output is correct
8 Incorrect 301 ms 26800 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 18428 KB Output is correct
2 Correct 266 ms 18432 KB Output is correct
3 Correct 329 ms 18464 KB Output is correct
4 Correct 374 ms 26740 KB Output is correct
5 Correct 282 ms 18848 KB Output is correct
6 Correct 401 ms 26432 KB Output is correct
7 Correct 382 ms 26392 KB Output is correct
8 Correct 399 ms 26612 KB Output is correct
9 Correct 257 ms 24568 KB Output is correct
10 Correct 364 ms 26128 KB Output is correct
11 Correct 356 ms 25920 KB Output is correct
12 Correct 421 ms 26020 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 272 ms 18424 KB Output is correct
3 Correct 300 ms 18512 KB Output is correct
4 Correct 292 ms 18492 KB Output is correct
5 Correct 292 ms 19324 KB Output is correct
6 Correct 305 ms 20032 KB Output is correct
7 Correct 276 ms 20280 KB Output is correct
8 Incorrect 301 ms 26800 KB Output isn't correct
9 Halted 0 ms 0 KB -