oj.uz

Submission #528426

# Submission time Handle Problem Language Result Execution time Memory
528426 2022-02-20T09:26:50 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 552 ms 32092 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]);
}

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);
    }

    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]);
    }

    for(int i = 1; i <= n; i++) nxt[i] = get(i, nxt[i] - 1);

    vector< int > vc;
    int i = 1;
    while(i <= n)
    {
        vc.pb(i);
        i = nxt[i];
    }

//    cout << endl;
//    for(auto u : vc) cout << u << endl;
//    cout << endl;

    cin >> q;
    while(q--)
    {
        int le, ri;
        cin >> le >> ri;
        int ans = 0;
        ans = 1; le = nxt[le]; ri = nxt[ri];
        if (le <= ri)
          {
              int skok1 = upper_bound(all(vc), ri) - vc.begin();
              int skok2 = lower_bound(all(vc), le) - vc.begin();
              ans += abs(skok2 - skok1);
              //cout << upper_bound(all(vc), ri) - vc.begin() << ' ' << lower_bound(all(vc), le) - vc.begin() << endl;
          }
//        int i = le, ans = 0;
//        while(i <= ri)
//        {
//            i = nxt[i];
//            ans++;
//        }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 30952 KB Output is correct
2 Correct 509 ms 30696 KB Output is correct
3 Correct 488 ms 30684 KB Output is correct
4 Correct 512 ms 30952 KB Output is correct
5 Correct 544 ms 31956 KB Output is correct
6 Correct 168 ms 21836 KB Output is correct
7 Correct 181 ms 21440 KB Output is correct
8 Correct 184 ms 21636 KB Output is correct
9 Correct 193 ms 21976 KB Output is correct
10 Correct 194 ms 20912 KB Output is correct
11 Correct 387 ms 30156 KB Output is correct
12 Correct 360 ms 28884 KB Output is correct
13 Correct 351 ms 28788 KB Output is correct
14 Correct 390 ms 30132 KB Output is correct
15 Correct 364 ms 29520 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 188 ms 23304 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 1224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 1224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 552 ms 32092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 30952 KB Output is correct
2 Correct 509 ms 30696 KB Output is correct
3 Correct 488 ms 30684 KB Output is correct
4 Correct 512 ms 30952 KB Output is correct
5 Correct 544 ms 31956 KB Output is correct
6 Correct 168 ms 21836 KB Output is correct
7 Correct 181 ms 21440 KB Output is correct
8 Correct 184 ms 21636 KB Output is correct
9 Correct 193 ms 21976 KB Output is correct
10 Correct 194 ms 20912 KB Output is correct
11 Correct 387 ms 30156 KB Output is correct
12 Correct 360 ms 28884 KB Output is correct
13 Correct 351 ms 28788 KB Output is correct
14 Correct 390 ms 30132 KB Output is correct
15 Correct 364 ms 29520 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 188 ms 23304 KB Output is correct
18 Incorrect 18 ms 1224 KB Output isn't correct
19 Halted 0 ms 0 KB -