oj.uz

Submission #588944

# Submission time Handle Problem Language Result Execution time Memory
588944 2022-07-04T08:05:10 Z ParsaEs Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 4612 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;
        }
        ll z = e[r].X, mx = -inf;
        bool f = 1;
        rep(i, r, y + 1)
        {
            if(z < e[i].X && mx < e[i].X)
            {
                f = 0;
                break;
            }
            if(z < e[i].X) z = mx, ans++;
            mx = max(mx, e[i].Y.X);
        }
        if(f) cout << ans << '\n';
        else cout << "impossible\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 211 ms 3656 KB Output is correct
3 Correct 197 ms 3808 KB Output is correct
4 Correct 145 ms 3836 KB Output is correct
5 Correct 200 ms 3960 KB Output is correct
6 Correct 229 ms 3896 KB Output is correct
7 Correct 232 ms 3972 KB Output is correct
8 Correct 49 ms 4612 KB Output is correct
9 Correct 49 ms 3960 KB Output is correct
10 Correct 760 ms 4264 KB Output is correct
11 Correct 1151 ms 4284 KB Output is correct
12 Correct 44 ms 4400 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3852 KB Output is correct
2 Correct 195 ms 3912 KB Output is correct
3 Correct 134 ms 3896 KB Output is correct
4 Correct 55 ms 4028 KB Output is correct
5 Correct 743 ms 4200 KB Output is correct
6 Correct 94 ms 3928 KB Output is correct
7 Correct 99 ms 3912 KB Output is correct
8 Correct 888 ms 4284 KB Output is correct
9 Correct 28 ms 3232 KB Output is correct
10 Correct 161 ms 3660 KB Output is correct
11 Execution timed out 1572 ms 3508 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 211 ms 3656 KB Output is correct
3 Correct 197 ms 3808 KB Output is correct
4 Correct 145 ms 3836 KB Output is correct
5 Correct 200 ms 3960 KB Output is correct
6 Correct 229 ms 3896 KB Output is correct
7 Correct 232 ms 3972 KB Output is correct
8 Correct 49 ms 4612 KB Output is correct
9 Correct 49 ms 3960 KB Output is correct
10 Correct 760 ms 4264 KB Output is correct
11 Correct 1151 ms 4284 KB Output is correct
12 Correct 44 ms 4400 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Halted 0 ms 0 KB -