oj.uz

Submission #528429

# Submission time Handle Problem Language Result Execution time Memory
528429 2022-02-20T09:33:41 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 522 ms 32004 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];
        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 452 ms 31048 KB Output is correct
2 Correct 423 ms 30648 KB Output is correct
3 Correct 440 ms 30776 KB Output is correct
4 Correct 417 ms 31020 KB Output is correct
5 Correct 522 ms 32004 KB Output is correct
6 Correct 83 ms 21856 KB Output is correct
7 Correct 77 ms 21476 KB Output is correct
8 Correct 83 ms 21580 KB Output is correct
9 Correct 120 ms 22100 KB Output is correct
10 Correct 101 ms 20972 KB Output is correct
11 Correct 298 ms 30012 KB Output is correct
12 Correct 334 ms 28688 KB Output is correct
13 Correct 281 ms 28680 KB Output is correct
14 Correct 315 ms 30108 KB Output is correct
15 Correct 312 ms 29524 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 95 ms 23236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1248 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 1248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 31048 KB Output is correct
2 Correct 423 ms 30648 KB Output is correct
3 Correct 440 ms 30776 KB Output is correct
4 Correct 417 ms 31020 KB Output is correct
5 Correct 522 ms 32004 KB Output is correct
6 Correct 83 ms 21856 KB Output is correct
7 Correct 77 ms 21476 KB Output is correct
8 Correct 83 ms 21580 KB Output is correct
9 Correct 120 ms 22100 KB Output is correct
10 Correct 101 ms 20972 KB Output is correct
11 Correct 298 ms 30012 KB Output is correct
12 Correct 334 ms 28688 KB Output is correct
13 Correct 281 ms 28680 KB Output is correct
14 Correct 315 ms 30108 KB Output is correct
15 Correct 312 ms 29524 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 95 ms 23236 KB Output is correct
18 Incorrect 9 ms 1248 KB Output isn't correct
19 Halted 0 ms 0 KB -