oj.uz

Submission #528409

# Submission time Handle Problem Language Result Execution time Memory
528409 2022-02-20T08:55:10 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 1000 ms 31004 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 5;
int n, l[N], r[N], q, nxt[N], mn[N][22], lg[N], t[8 * N], mod[8 * N], mx;
vector<int> vec;

bool intersect(const pair<int, int> &a, const pair<int, int> &b)
{
    int L = max(a.fi, b.fi);
    int R = min(a.sd, b.sd);
    return R >= L;
}

int get(int l, int r)
{
    int t = lg[r - l + 1];
    return min(mn[l][t], mn[r - (1 << t) + 1][t]);
}

void push(int v, int tl, int tr)
{
    if (tl == tr) return;
    t[v + v] = min(t[v + v], mod[v]);
    t[v + v + 1] = min(t[v + v + 1], mod[v]);
    mod[v] = n + 1;
}

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = n + 1;
        mod[v] = n + 1;
        return;
    }

    int m = (tl + tr) >> 1;
    build(v + v, tl, m);
    build(v + v + 1, m + 1, tr);
    t[v] = min(t[v + v], t[v + v + 1]);
    mod[v] = n + 1;
}

int get(int v, int tl, int tr, int l, int r)
{
    push(v, tl, tr);
    if (tl > tr || tl > r || tr < l) return n + 1;

    if (tl >= l && tr <= r)
      return t[v];

    //push(v, tl, tr);
    int m = (tl + tr) >> 1;
    return min(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
}

void upd(int v, int tl, int tr, int l, int r, int val)
{
    push(v, tl, tr);
    if (tl > tr || tl > r || tr < l) return;

    if (tl >= l && tr <= r)
    {
        t[v] = val;
        mod[v] = val;
        //push(v, tl, tr);
        return;
    }

    int m = (tl + tr) >> 1;
    //push(v, tl, tr);
    upd(v + v, tl, m, l, r, val);
    upd(v + v + 1, m + 1, tr, l, r, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    lg[1] = 0;
    for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for(int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
        vec.pb(l[i]);
        vec.pb(r[i]);
    }

    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());
    for(int i = 1; i <= n; i++)
    {
        l[i] = lower_bound(all(vec), l[i]) - vec.begin(); l[i]++;
        r[i] = lower_bound(all(vec), r[i]) - vec.begin(); r[i]++;
        mx = max(mx, l[i]);
        mx = max(mx, r[i]);
    }

    build(1, 1, mx);
    for(int i = n; i >= 1; i--)
    {
        /*
        int val = get(1, 1, mx, l[i], r[i]);
        nxt[i] = val;

        mn[i][0] = nxt[i];
        upd(1, 1, mx, l[i], r[i], i);
        */
        bool ok = 0;
        for(int j = i + 1; j <= n; j++)
          if (intersect({l[i], r[i]}, {l[j], r[j]}))
            {
                nxt[i] = j;
                ok = 1;
                break;
            }

        if (!ok) nxt[i] = n + 1;
        mn[i][0] = nxt[i];
    }

    for(int i = 1; (1 << i) <= n; i++)
    {
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
          mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
    }

//    cout << endl;
//    for(int i = 1; i <= n; i++) cout << nxt[i] << ' ';
//    cout << endl;
    cin >> q;
    while(q--)
    {
        int le, ri;
        cin >> le >> ri;
        int i = le, ans = 0;
        while(i <= ri)
        {
            int mn = get(i, nxt[i] - 1);
            mn = min(mn, ri + 1);
            ans++;
            i = mn;
        }

        cout << ans << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 29524 KB Output is correct
2 Correct 258 ms 29804 KB Output is correct
3 Correct 272 ms 29816 KB Output is correct
4 Correct 262 ms 30000 KB Output is correct
5 Correct 306 ms 31004 KB Output is correct
6 Correct 194 ms 20816 KB Output is correct
7 Correct 172 ms 21104 KB Output is correct
8 Correct 201 ms 21280 KB Output is correct
9 Correct 185 ms 21728 KB Output is correct
10 Correct 171 ms 21132 KB Output is correct
11 Execution timed out 1072 ms 16696 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1208 KB Output is correct
2 Correct 77 ms 1160 KB Output is correct
3 Correct 75 ms 1228 KB Output is correct
4 Correct 77 ms 1100 KB Output is correct
5 Correct 81 ms 1160 KB Output is correct
6 Correct 100 ms 952 KB Output is correct
7 Correct 69 ms 908 KB Output is correct
8 Correct 61 ms 940 KB Output is correct
9 Correct 50 ms 908 KB Output is correct
10 Correct 43 ms 844 KB Output is correct
11 Correct 27 ms 1100 KB Output is correct
12 Correct 28 ms 1156 KB Output is correct
13 Correct 27 ms 1068 KB Output is correct
14 Correct 25 ms 1156 KB Output is correct
15 Correct 26 ms 1216 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 298 ms 1044 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1208 KB Output is correct
2 Correct 77 ms 1160 KB Output is correct
3 Correct 75 ms 1228 KB Output is correct
4 Correct 77 ms 1100 KB Output is correct
5 Correct 81 ms 1160 KB Output is correct
6 Correct 100 ms 952 KB Output is correct
7 Correct 69 ms 908 KB Output is correct
8 Correct 61 ms 940 KB Output is correct
9 Correct 50 ms 908 KB Output is correct
10 Correct 43 ms 844 KB Output is correct
11 Correct 27 ms 1100 KB Output is correct
12 Correct 28 ms 1156 KB Output is correct
13 Correct 27 ms 1068 KB Output is correct
14 Correct 25 ms 1156 KB Output is correct
15 Correct 26 ms 1216 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 298 ms 1044 KB Output is correct
18 Execution timed out 1083 ms 1464 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 30540 KB Output is correct
2 Correct 393 ms 30628 KB Output is correct
3 Correct 316 ms 29272 KB Output is correct
4 Correct 355 ms 29012 KB Output is correct
5 Correct 345 ms 29680 KB Output is correct
6 Correct 266 ms 21024 KB Output is correct
7 Correct 276 ms 20832 KB Output is correct
8 Correct 239 ms 21136 KB Output is correct
9 Correct 297 ms 20892 KB Output is correct
10 Correct 278 ms 22444 KB Output is correct
11 Execution timed out 1053 ms 16272 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 29524 KB Output is correct
2 Correct 258 ms 29804 KB Output is correct
3 Correct 272 ms 29816 KB Output is correct
4 Correct 262 ms 30000 KB Output is correct
5 Correct 306 ms 31004 KB Output is correct
6 Correct 194 ms 20816 KB Output is correct
7 Correct 172 ms 21104 KB Output is correct
8 Correct 201 ms 21280 KB Output is correct
9 Correct 185 ms 21728 KB Output is correct
10 Correct 171 ms 21132 KB Output is correct
11 Execution timed out 1072 ms 16696 KB Time limit exceeded
12 Halted 0 ms 0 KB -