oj.uz

Submission #528420

# Submission time Handle Problem Language Result Execution time Memory
528420 2022-02-20T09:03:44 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
40 / 110
 1000 ms 33716 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;
    mod[v + v] = min(mod[v + v], mod[v]);
    mod[v + v + 1] = min(mod[v + v + 1], mod[v]);
    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] = min(t[v], val);
        mod[v] = min(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 29480 KB Output is correct
2 Correct 569 ms 29200 KB Output is correct
3 Correct 539 ms 29288 KB Output is correct
4 Correct 550 ms 29536 KB Output is correct
5 Correct 555 ms 30444 KB Output is correct
6 Correct 171 ms 20424 KB Output is correct
7 Correct 179 ms 20616 KB Output is correct
8 Correct 199 ms 20800 KB Output is correct
9 Correct 194 ms 21332 KB Output is correct
10 Correct 194 ms 20628 KB Output is correct
11 Correct 417 ms 30048 KB Output is correct
12 Correct 382 ms 31776 KB Output is correct
13 Correct 369 ms 31616 KB Output is correct
14 Correct 481 ms 33312 KB Output is correct
15 Correct 384 ms 32576 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 182 ms 25396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1196 KB Output is correct
2 Correct 83 ms 1160 KB Output is correct
3 Correct 79 ms 1168 KB Output is correct
4 Correct 79 ms 1188 KB Output is correct
5 Correct 80 ms 1148 KB Output is correct
6 Correct 100 ms 940 KB Output is correct
7 Correct 69 ms 904 KB Output is correct
8 Correct 61 ms 1120 KB Output is correct
9 Correct 53 ms 1040 KB Output is correct
10 Correct 39 ms 920 KB Output is correct
11 Correct 15 ms 1100 KB Output is correct
12 Correct 15 ms 1100 KB Output is correct
13 Correct 21 ms 1192 KB Output is correct
14 Correct 16 ms 1204 KB Output is correct
15 Correct 20 ms 1216 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 267 ms 932 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1196 KB Output is correct
2 Correct 83 ms 1160 KB Output is correct
3 Correct 79 ms 1168 KB Output is correct
4 Correct 79 ms 1188 KB Output is correct
5 Correct 80 ms 1148 KB Output is correct
6 Correct 100 ms 940 KB Output is correct
7 Correct 69 ms 904 KB Output is correct
8 Correct 61 ms 1120 KB Output is correct
9 Correct 53 ms 1040 KB Output is correct
10 Correct 39 ms 920 KB Output is correct
11 Correct 15 ms 1100 KB Output is correct
12 Correct 15 ms 1100 KB Output is correct
13 Correct 21 ms 1192 KB Output is correct
14 Correct 16 ms 1204 KB Output is correct
15 Correct 20 ms 1216 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 267 ms 932 KB Output is correct
18 Execution timed out 1083 ms 1612 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 30448 KB Output is correct
2 Correct 582 ms 30000 KB Output is correct
3 Correct 555 ms 28540 KB Output is correct
4 Correct 674 ms 28528 KB Output is correct
5 Correct 645 ms 29052 KB Output is correct
6 Correct 230 ms 20404 KB Output is correct
7 Correct 240 ms 20188 KB Output is correct
8 Correct 232 ms 20404 KB Output is correct
9 Correct 235 ms 20216 KB Output is correct
10 Correct 353 ms 21808 KB Output is correct
11 Correct 373 ms 28572 KB Output is correct
12 Correct 398 ms 33716 KB Output is correct
13 Correct 383 ms 31544 KB Output is correct
14 Correct 367 ms 32200 KB Output is correct
15 Correct 403 ms 33628 KB Output is correct
16 Correct 1 ms 284 KB Output is correct
17 Correct 409 ms 24368 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 29480 KB Output is correct
2 Correct 569 ms 29200 KB Output is correct
3 Correct 539 ms 29288 KB Output is correct
4 Correct 550 ms 29536 KB Output is correct
5 Correct 555 ms 30444 KB Output is correct
6 Correct 171 ms 20424 KB Output is correct
7 Correct 179 ms 20616 KB Output is correct
8 Correct 199 ms 20800 KB Output is correct
9 Correct 194 ms 21332 KB Output is correct
10 Correct 194 ms 20628 KB Output is correct
11 Correct 417 ms 30048 KB Output is correct
12 Correct 382 ms 31776 KB Output is correct
13 Correct 369 ms 31616 KB Output is correct
14 Correct 481 ms 33312 KB Output is correct
15 Correct 384 ms 32576 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 182 ms 25396 KB Output is correct
18 Correct 92 ms 1196 KB Output is correct
19 Correct 83 ms 1160 KB Output is correct
20 Correct 79 ms 1168 KB Output is correct
21 Correct 79 ms 1188 KB Output is correct
22 Correct 80 ms 1148 KB Output is correct
23 Correct 100 ms 940 KB Output is correct
24 Correct 69 ms 904 KB Output is correct
25 Correct 61 ms 1120 KB Output is correct
26 Correct 53 ms 1040 KB Output is correct
27 Correct 39 ms 920 KB Output is correct
28 Correct 15 ms 1100 KB Output is correct
29 Correct 15 ms 1100 KB Output is correct
30 Correct 21 ms 1192 KB Output is correct
31 Correct 16 ms 1204 KB Output is correct
32 Correct 20 ms 1216 KB Output is correct
33 Correct 0 ms 332 KB Output is correct
34 Correct 267 ms 932 KB Output is correct
35 Execution timed out 1083 ms 1612 KB Time limit exceeded
36 Halted 0 ms 0 KB -