oj.uz

Submission #588926

# Submission time Handle Problem Language Result Execution time Memory
588926 2022-07-04T07:45:26 Z ParsaEs Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 4104 KB 
//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "Ofast", "O3")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, l, r) for(ll i = l; i < r; i++)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pi;
constexpr ll inf = 2e9, xn = 1e5 + 5, s = 317;
ll d[xn], p[xn], sx[xn], x[xn], m[s];
pi e[xn];
int main()
{
    Fast
    ll n, q;
    cin >> n >> q;
    rep(i, 0, n) cin >> e[i].Y.X >> e[i].X;
    rep(i, 0, n) e[i] = {-e[i].X, {-e[i].Y.X, i}};
    sort(e, e + n);
    rep(i, 0, s) m[i] = -inf;
    rep(i, 0, n)
    {
        sx[i] = x[i] = -1;
        rep(j, 0, i / s + 1) if(e[i].X <= m[j])
        {
            rep(k, j * s, min((j + 1) * s, i)) if(e[i].X <= e[k].Y.X)
            {
                if(k / s < i / s) sx[i] = k, d[i] = 1;
                else if(sx[k] >= 0) sx[i] = sx[k], d[i] = d[k] + 1;
                x[i] = k;
                break;
            }
            break;
        }
        m[i / s] = max(e[i].Y.X, m[i / s]), p[e[i].Y.Y] = i;
    }
    while(q--)
    {
        ll l, r, ans = 0;
        cin >> l >> r;
        if(l == r)
        {
            cout << "0\n";
            continue;
        }
        l = p[l - 1], r = p[r - 1];
        if(e[l].X < e[r].X)
        {
            cout << "impossible\n";
            continue;
        }
        if(e[l].X == e[r].X)
        {
            cout << "1\n";
            continue;
        }
        ll y = l;
        while(sx[y] >= r) ans += d[y], y = sx[y];
        while(x[y] >= r) y = x[y], ans++;
        if(r == y)
        {
            cout << ans << '\n';
            continue;
        }
        bool f = 0;
        rep(i, r, y) if(e[y].X <= e[i].Y.X)
        {
            ans++, f = 1;
            break;
        }
        if(f) cout << ans << '\n';
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 226 ms 3828 KB Output is correct
3 Correct 203 ms 4008 KB Output is correct
4 Correct 138 ms 3940 KB Output is correct
5 Correct 216 ms 3976 KB Output is correct
6 Correct 241 ms 4104 KB Output is correct
7 Correct 226 ms 4036 KB Output is correct
8 Execution timed out 1533 ms 3916 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 3984 KB Output is correct
2 Correct 185 ms 4004 KB Output is correct
3 Correct 132 ms 3908 KB Output is correct
4 Execution timed out 1548 ms 3600 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 226 ms 3828 KB Output is correct
3 Correct 203 ms 4008 KB Output is correct
4 Correct 138 ms 3940 KB Output is correct
5 Correct 216 ms 3976 KB Output is correct
6 Correct 241 ms 4104 KB Output is correct
7 Correct 226 ms 4036 KB Output is correct
8 Execution timed out 1533 ms 3916 KB Time limit exceeded
9 Halted 0 ms 0 KB -