oj.uz

Submission #578079

# Submission time Handle Problem Language Result Execution time Memory
578079 2022-06-16T03:19:59 Z balbit Event Hopping (BOI22_events) C++14
20 / 100
 207 ms 29700 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n)  FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T,typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e5+5;
vector<pii> to[maxn]; // {lpos,id}

vector<pii> ask[maxn]; // for each seg id, the left pos and the queryid
int ans[maxn];
int fa[18][maxn];
struct seg{
    int l,r,i;
};

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    bug(1,2);

    int n,q; cin>>n>>q;
    vector<pii>v(n);
    vector<ll>xpos;
    REP(i,n) {
        cin>>v[i].f>>v[i].s;
        xpos.pb(v[i].f);
        xpos.pb(v[i].s);
    }
    sort(ALL(xpos)); xpos.resize(unique(ALL(xpos)) - xpos.begin());

    auto getx = [&](ll x) {return lower_bound(ALL(xpos), x)-xpos.begin();};

    REP(i,n) {
        v[i].f = getx(v[i].f);
        v[i].s = getx(v[i].s);
        to[v[i].s].pb({v[i].f,i});
    }

    REP(i,q) {
        int s,e; cin>>s>>e; --s; --e;
        if (s == e) {
            ans[i] = 0; continue;
        }
        ask[e].pb({v[s].s,i});
    }

    vector<seg> now;

    REP(r, maxn)  {
        sort(ALL(to[r]));
        for (pii T : to[r]) {
            int l= T.f, i =T.s;
            while (SZ(now) >= 2 && l <= now[SZ(now)-2].r) now.pop_back();
            if (SZ(now) && now.back().r >= l) {
                fa[0][i] = now.back().i;
            }else{
                fa[0][i] = i;
            }
            for (int j = 1; j<18; ++j) {
                fa[j][i] = fa[j-1][fa[j-1][i]];
            }
            now.pb({l,r,i});

            for (pii qq : ask[i]) {
                if (qq.f > r) {
                    ans[qq.s] = -1; continue;
                }
                int steps =0;
                int at = i;
                for (int j = 17; j>=0; --j) {
                    if (v[fa[j][at]].f > qq.f) {
                        steps += (1<<j);
                        at = fa[j][at];
                    }
                }
                if (v[at].f > qq.f) {
                    at = fa[0][at]; ++steps;
                }
                if (v[at].f > qq.f) {
                    ans[qq.s] = -1;
                }else{
                    ans[qq.s] = steps+1;
                }
            }
        }
    }
    REP(i,q) {
        if (ans[i] == -1) cout<<"impossible"<<endl;
        else cout<<ans[i]<<endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 127 ms 28372 KB Output is correct
3 Correct 127 ms 28972 KB Output is correct
4 Correct 207 ms 29176 KB Output is correct
5 Correct 123 ms 28876 KB Output is correct
6 Correct 133 ms 28808 KB Output is correct
7 Correct 127 ms 28812 KB Output is correct
8 Correct 122 ms 29516 KB Output is correct
9 Correct 124 ms 29520 KB Output is correct
10 Correct 172 ms 29700 KB Output is correct
11 Correct 177 ms 28564 KB Output is correct
12 Correct 69 ms 28012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9900 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Correct 7 ms 9884 KB Output is correct
6 Correct 7 ms 9960 KB Output is correct
7 Correct 7 ms 9896 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9900 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Correct 7 ms 9884 KB Output is correct
6 Correct 7 ms 9960 KB Output is correct
7 Correct 7 ms 9896 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9716 KB Output is correct
12 Correct 8 ms 9940 KB Output is correct
13 Correct 7 ms 9940 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 6 ms 9856 KB Output is correct
16 Correct 6 ms 9964 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 7 ms 9940 KB Output is correct
19 Correct 34 ms 13612 KB Output is correct
20 Correct 36 ms 13644 KB Output is correct
21 Correct 40 ms 14516 KB Output is correct
22 Incorrect 34 ms 14344 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 7 ms 9900 KB Output is correct
4 Correct 7 ms 9920 KB Output is correct
5 Correct 7 ms 9884 KB Output is correct
6 Correct 7 ms 9960 KB Output is correct
7 Correct 7 ms 9896 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9940 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Correct 6 ms 9984 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Correct 7 ms 9940 KB Output is correct
17 Correct 7 ms 9956 KB Output is correct
18 Correct 6 ms 9940 KB Output is correct
19 Correct 107 ms 26820 KB Output is correct
20 Correct 104 ms 26088 KB Output is correct
21 Incorrect 97 ms 22612 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 28332 KB Output is correct
2 Correct 133 ms 29020 KB Output is correct
3 Correct 167 ms 29248 KB Output is correct
4 Correct 124 ms 29500 KB Output is correct
5 Correct 178 ms 29684 KB Output is correct
6 Incorrect 161 ms 26824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 127 ms 28372 KB Output is correct
3 Correct 127 ms 28972 KB Output is correct
4 Correct 207 ms 29176 KB Output is correct
5 Correct 123 ms 28876 KB Output is correct
6 Correct 133 ms 28808 KB Output is correct
7 Correct 127 ms 28812 KB Output is correct
8 Correct 122 ms 29516 KB Output is correct
9 Correct 124 ms 29520 KB Output is correct
10 Correct 172 ms 29700 KB Output is correct
11 Correct 177 ms 28564 KB Output is correct
12 Correct 69 ms 28012 KB Output is correct
13 Correct 6 ms 9940 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 7 ms 9900 KB Output is correct
16 Correct 7 ms 9920 KB Output is correct
17 Correct 7 ms 9884 KB Output is correct
18 Correct 7 ms 9960 KB Output is correct
19 Correct 7 ms 9896 KB Output is correct
20 Correct 7 ms 9940 KB Output is correct
21 Correct 6 ms 9940 KB Output is correct
22 Correct 6 ms 9812 KB Output is correct
23 Correct 6 ms 9716 KB Output is correct
24 Correct 8 ms 9940 KB Output is correct
25 Correct 7 ms 9940 KB Output is correct
26 Correct 6 ms 9940 KB Output is correct
27 Correct 6 ms 9856 KB Output is correct
28 Correct 6 ms 9964 KB Output is correct
29 Correct 7 ms 9940 KB Output is correct
30 Correct 7 ms 9940 KB Output is correct
31 Correct 34 ms 13612 KB Output is correct
32 Correct 36 ms 13644 KB Output is correct
33 Correct 40 ms 14516 KB Output is correct
34 Incorrect 34 ms 14344 KB Output isn't correct
35 Halted 0 ms 0 KB -