oj.uz

Submission #528428

# Submission time Handle Problem Language Result Execution time Memory
528428 2022-02-20T09:30:33 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 462 ms 31952 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 = lower_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 437 ms 31032 KB Output is correct
2 Correct 428 ms 30732 KB Output is correct
3 Correct 409 ms 30704 KB Output is correct
4 Correct 462 ms 31056 KB Output is correct
5 Correct 414 ms 31932 KB Output is correct
6 Correct 70 ms 21912 KB Output is correct
7 Correct 79 ms 21468 KB Output is correct
8 Correct 88 ms 21772 KB Output is correct
9 Correct 98 ms 21984 KB Output is correct
10 Correct 102 ms 20916 KB Output is correct
11 Correct 318 ms 30096 KB Output is correct
12 Correct 280 ms 28748 KB Output is correct
13 Correct 289 ms 28732 KB Output is correct
14 Correct 326 ms 30028 KB Output is correct
15 Correct 320 ms 29472 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 75 ms 23204 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 31032 KB Output is correct
2 Correct 428 ms 30732 KB Output is correct
3 Correct 409 ms 30704 KB Output is correct
4 Correct 462 ms 31056 KB Output is correct
5 Correct 414 ms 31932 KB Output is correct
6 Correct 70 ms 21912 KB Output is correct
7 Correct 79 ms 21468 KB Output is correct
8 Correct 88 ms 21772 KB Output is correct
9 Correct 98 ms 21984 KB Output is correct
10 Correct 102 ms 20916 KB Output is correct
11 Correct 318 ms 30096 KB Output is correct
12 Correct 280 ms 28748 KB Output is correct
13 Correct 289 ms 28732 KB Output is correct
14 Correct 326 ms 30028 KB Output is correct
15 Correct 320 ms 29472 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 75 ms 23204 KB Output is correct
18 Incorrect 9 ms 1228 KB Output isn't correct
19 Halted 0 ms 0 KB -