oj.uz

Submission #528363

# Submission time Handle Problem Language Result Execution time Memory
528363 2022-02-20T07:31:55 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
0 / 110
 1000 ms 6496 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], 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.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 6140 KB Output is correct
2 Correct 160 ms 6096 KB Output is correct
3 Correct 146 ms 6088 KB Output is correct
4 Correct 137 ms 6212 KB Output is correct
5 Correct 149 ms 6388 KB Output is correct
6 Correct 73 ms 5956 KB Output is correct
7 Correct 90 ms 6064 KB Output is correct
8 Correct 64 ms 6072 KB Output is correct
9 Correct 63 ms 6132 KB Output is correct
10 Correct 60 ms 6036 KB Output is correct
11 Execution timed out 1053 ms 3780 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 676 KB Output is correct
2 Correct 650 ms 580 KB Output is correct
3 Correct 562 ms 560 KB Output is correct
4 Correct 568 ms 600 KB Output is correct
5 Correct 575 ms 548 KB Output is correct
6 Correct 730 ms 564 KB Output is correct
7 Correct 537 ms 556 KB Output is correct
8 Correct 437 ms 688 KB Output is correct
9 Correct 377 ms 556 KB Output is correct
10 Correct 244 ms 556 KB Output is correct
11 Correct 16 ms 496 KB Output is correct
12 Correct 19 ms 488 KB Output is correct
13 Correct 15 ms 460 KB Output is correct
14 Correct 18 ms 460 KB Output is correct
15 Correct 17 ms 588 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Execution timed out 1078 ms 552 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 676 KB Output is correct
2 Correct 650 ms 580 KB Output is correct
3 Correct 562 ms 560 KB Output is correct
4 Correct 568 ms 600 KB Output is correct
5 Correct 575 ms 548 KB Output is correct
6 Correct 730 ms 564 KB Output is correct
7 Correct 537 ms 556 KB Output is correct
8 Correct 437 ms 688 KB Output is correct
9 Correct 377 ms 556 KB Output is correct
10 Correct 244 ms 556 KB Output is correct
11 Correct 16 ms 496 KB Output is correct
12 Correct 19 ms 488 KB Output is correct
13 Correct 15 ms 460 KB Output is correct
14 Correct 18 ms 460 KB Output is correct
15 Correct 17 ms 588 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Execution timed out 1078 ms 552 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 6496 KB Output is correct
2 Correct 772 ms 6328 KB Output is correct
3 Correct 785 ms 5948 KB Output is correct
4 Correct 652 ms 5980 KB Output is correct
5 Correct 670 ms 6056 KB Output is correct
6 Correct 725 ms 6004 KB Output is correct
7 Correct 679 ms 6104 KB Output is correct
8 Correct 484 ms 6072 KB Output is correct
9 Correct 380 ms 5948 KB Output is correct
10 Correct 355 ms 6280 KB Output is correct
11 Execution timed out 1034 ms 3504 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 6140 KB Output is correct
2 Correct 160 ms 6096 KB Output is correct
3 Correct 146 ms 6088 KB Output is correct
4 Correct 137 ms 6212 KB Output is correct
5 Correct 149 ms 6388 KB Output is correct
6 Correct 73 ms 5956 KB Output is correct
7 Correct 90 ms 6064 KB Output is correct
8 Correct 64 ms 6072 KB Output is correct
9 Correct 63 ms 6132 KB Output is correct
10 Correct 60 ms 6036 KB Output is correct
11 Execution timed out 1053 ms 3780 KB Time limit exceeded
12 Halted 0 ms 0 KB -