oj.uz

Submission #528408

# Submission time Handle Problem Language Result Execution time Memory
528408 2022-02-20T08:53:36 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 1000 ms 28532 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[4 * N], mod[4 * 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 Execution timed out 1098 ms 27568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1204 KB Output is correct
2 Correct 75 ms 1308 KB Output is correct
3 Correct 72 ms 1228 KB Output is correct
4 Correct 80 ms 1352 KB Output is correct
5 Correct 74 ms 1300 KB Output is correct
6 Correct 95 ms 1092 KB Output is correct
7 Correct 67 ms 1040 KB Output is correct
8 Correct 58 ms 972 KB Output is correct
9 Correct 51 ms 972 KB Output is correct
10 Correct 40 ms 1060 KB Output is correct
11 Correct 26 ms 1300 KB Output is correct
12 Correct 25 ms 1164 KB Output is correct
13 Correct 24 ms 1184 KB Output is correct
14 Correct 25 ms 1296 KB Output is correct
15 Correct 26 ms 1208 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 263 ms 1048 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1204 KB Output is correct
2 Correct 75 ms 1308 KB Output is correct
3 Correct 72 ms 1228 KB Output is correct
4 Correct 80 ms 1352 KB Output is correct
5 Correct 74 ms 1300 KB Output is correct
6 Correct 95 ms 1092 KB Output is correct
7 Correct 67 ms 1040 KB Output is correct
8 Correct 58 ms 972 KB Output is correct
9 Correct 51 ms 972 KB Output is correct
10 Correct 40 ms 1060 KB Output is correct
11 Correct 26 ms 1300 KB Output is correct
12 Correct 25 ms 1164 KB Output is correct
13 Correct 24 ms 1184 KB Output is correct
14 Correct 25 ms 1296 KB Output is correct
15 Correct 26 ms 1208 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 263 ms 1048 KB Output is correct
18 Execution timed out 1093 ms 1596 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 28532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 27568 KB Time limit exceeded
2 Halted 0 ms 0 KB -