제출 #528363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528363		N1NT3NDO	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	1078 ms	6496 KiB

Main

#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], t[4 * N];
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;
}

void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v] = nxt[tl];
        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]);
}

int get(int v, int tl, int tr, int l, int r)
{
    if (tl > tr || tl > r || tr < l) return 1e9;
    if (tl >= l && tr <= r)
      return t[v];

    int m = (tl + tr) >> 1;

    return min(get(v + v, tl, m, l, r), get(v + v + 1, m + 1, tr, l, r));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    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]++;
    }

    for(int i = 1; i <= n; 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;
    }

    build(1, 1, n);
    cin >> q;
    while(q--)
    {
        int le, ri;
        cin >> le >> ri;
        int i = le, ans = 0;
        while(i <= ri)
        {
            int mn = get(1, 1, n, i, nxt[i] - 1);
            mn = min(mn, ri + 1);
            ans++;
            i = mn;
        }

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50