oj.uz

Submission #528367

# Submission time Handle Problem Language Result Execution time Memory
528367 2022-02-20T07:38:56 Z N1NT3NDO Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 1000 ms 22284 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];
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]);
}

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]++;
    }

    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;
        mn[i][0] = nxt[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]);
    }

    cin >> q;
    while(q--)
    {
        int le, ri;
        cin >> le >> ri;
        int i = le, ans = 0;
        while(i <= ri)
        {
            int mn = get(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 161 ms 21344 KB Output is correct
2 Correct 147 ms 21064 KB Output is correct
3 Correct 152 ms 21140 KB Output is correct
4 Correct 154 ms 21340 KB Output is correct
5 Correct 164 ms 22212 KB Output is correct
6 Correct 68 ms 20264 KB Output is correct
7 Correct 79 ms 20668 KB Output is correct
8 Correct 81 ms 20792 KB Output is correct
9 Correct 83 ms 21340 KB Output is correct
10 Correct 86 ms 20648 KB Output is correct
11 Execution timed out 1088 ms 4816 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 956 KB Output is correct
2 Correct 64 ms 916 KB Output is correct
3 Correct 63 ms 916 KB Output is correct
4 Correct 64 ms 948 KB Output is correct
5 Correct 63 ms 844 KB Output is correct
6 Correct 86 ms 952 KB Output is correct
7 Correct 63 ms 920 KB Output is correct
8 Correct 51 ms 952 KB Output is correct
9 Correct 40 ms 920 KB Output is correct
10 Correct 28 ms 1052 KB Output is correct
11 Correct 16 ms 972 KB Output is correct
12 Correct 14 ms 860 KB Output is correct
13 Correct 14 ms 928 KB Output is correct
14 Correct 16 ms 852 KB Output is correct
15 Correct 16 ms 924 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 253 ms 932 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 956 KB Output is correct
2 Correct 64 ms 916 KB Output is correct
3 Correct 63 ms 916 KB Output is correct
4 Correct 64 ms 948 KB Output is correct
5 Correct 63 ms 844 KB Output is correct
6 Correct 86 ms 952 KB Output is correct
7 Correct 63 ms 920 KB Output is correct
8 Correct 51 ms 952 KB Output is correct
9 Correct 40 ms 920 KB Output is correct
10 Correct 28 ms 1052 KB Output is correct
11 Correct 16 ms 972 KB Output is correct
12 Correct 14 ms 860 KB Output is correct
13 Correct 14 ms 928 KB Output is correct
14 Correct 16 ms 852 KB Output is correct
15 Correct 16 ms 924 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 253 ms 932 KB Output is correct
18 Execution timed out 1097 ms 1260 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 22284 KB Output is correct
2 Correct 224 ms 21828 KB Output is correct
3 Correct 224 ms 20404 KB Output is correct
4 Correct 191 ms 20120 KB Output is correct
5 Correct 210 ms 20768 KB Output is correct
6 Correct 139 ms 20364 KB Output is correct
7 Correct 144 ms 20252 KB Output is correct
8 Correct 132 ms 20472 KB Output is correct
9 Correct 127 ms 20236 KB Output is correct
10 Correct 170 ms 21816 KB Output is correct
11 Execution timed out 1084 ms 4572 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 21344 KB Output is correct
2 Correct 147 ms 21064 KB Output is correct
3 Correct 152 ms 21140 KB Output is correct
4 Correct 154 ms 21340 KB Output is correct
5 Correct 164 ms 22212 KB Output is correct
6 Correct 68 ms 20264 KB Output is correct
7 Correct 79 ms 20668 KB Output is correct
8 Correct 81 ms 20792 KB Output is correct
9 Correct 83 ms 21340 KB Output is correct
10 Correct 86 ms 20648 KB Output is correct
11 Execution timed out 1088 ms 4816 KB Time limit exceeded
12 Halted 0 ms 0 KB -