oj.uz

Submission #528427

# Submission time Handle Problem Language Result Execution time Memory
528427 2022-02-20T09:27:17 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 454 ms 31976 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 403 ms 31072 KB Output is correct
2 Correct 401 ms 30764 KB Output is correct
3 Correct 389 ms 30800 KB Output is correct
4 Correct 405 ms 31020 KB Output is correct
5 Correct 412 ms 31888 KB Output is correct
6 Correct 75 ms 21816 KB Output is correct
7 Correct 77 ms 21464 KB Output is correct
8 Correct 82 ms 21648 KB Output is correct
9 Correct 91 ms 22008 KB Output is correct
10 Correct 94 ms 20936 KB Output is correct
11 Correct 294 ms 30216 KB Output is correct
12 Correct 269 ms 28696 KB Output is correct
13 Correct 272 ms 28704 KB Output is correct
14 Correct 296 ms 30144 KB Output is correct
15 Correct 287 ms 29528 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 74 ms 23272 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 31072 KB Output is correct
2 Correct 401 ms 30764 KB Output is correct
3 Correct 389 ms 30800 KB Output is correct
4 Correct 405 ms 31020 KB Output is correct
5 Correct 412 ms 31888 KB Output is correct
6 Correct 75 ms 21816 KB Output is correct
7 Correct 77 ms 21464 KB Output is correct
8 Correct 82 ms 21648 KB Output is correct
9 Correct 91 ms 22008 KB Output is correct
10 Correct 94 ms 20936 KB Output is correct
11 Correct 294 ms 30216 KB Output is correct
12 Correct 269 ms 28696 KB Output is correct
13 Correct 272 ms 28704 KB Output is correct
14 Correct 296 ms 30144 KB Output is correct
15 Correct 287 ms 29528 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 74 ms 23272 KB Output is correct
18 Incorrect 9 ms 1140 KB Output isn't correct
19 Halted 0 ms 0 KB -