oj.uz

Submission #528362

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

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 7876 KB Output is correct
2 Correct 134 ms 7760 KB Output is correct
3 Correct 168 ms 7704 KB Output is correct
4 Correct 138 ms 7780 KB Output is correct
5 Correct 144 ms 8208 KB Output is correct
6 Correct 43 ms 7528 KB Output is correct
7 Correct 56 ms 7584 KB Output is correct
8 Correct 56 ms 7600 KB Output is correct
9 Correct 76 ms 7720 KB Output is correct
10 Correct 58 ms 7480 KB Output is correct
11 Execution timed out 1036 ms 6752 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 580 KB Output is correct
2 Correct 40 ms 628 KB Output is correct
3 Correct 38 ms 628 KB Output is correct
4 Correct 47 ms 588 KB Output is correct
5 Correct 44 ms 620 KB Output is correct
6 Correct 37 ms 576 KB Output is correct
7 Correct 37 ms 620 KB Output is correct
8 Correct 40 ms 632 KB Output is correct
9 Correct 39 ms 708 KB Output is correct
10 Correct 38 ms 580 KB Output is correct
11 Correct 39 ms 600 KB Output is correct
12 Correct 34 ms 588 KB Output is correct
13 Correct 30 ms 580 KB Output is correct
14 Correct 44 ms 592 KB Output is correct
15 Correct 38 ms 584 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 118 ms 620 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 580 KB Output is correct
2 Correct 40 ms 628 KB Output is correct
3 Correct 38 ms 628 KB Output is correct
4 Correct 47 ms 588 KB Output is correct
5 Correct 44 ms 620 KB Output is correct
6 Correct 37 ms 576 KB Output is correct
7 Correct 37 ms 620 KB Output is correct
8 Correct 40 ms 632 KB Output is correct
9 Correct 39 ms 708 KB Output is correct
10 Correct 38 ms 580 KB Output is correct
11 Correct 39 ms 600 KB Output is correct
12 Correct 34 ms 588 KB Output is correct
13 Correct 30 ms 580 KB Output is correct
14 Correct 44 ms 592 KB Output is correct
15 Correct 38 ms 584 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 118 ms 620 KB Output is correct
18 Execution timed out 1072 ms 2648 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 8212 KB Output is correct
2 Correct 169 ms 8004 KB Output is correct
3 Correct 178 ms 7536 KB Output is correct
4 Correct 161 ms 7428 KB Output is correct
5 Correct 179 ms 7724 KB Output is correct
6 Correct 67 ms 7480 KB Output is correct
7 Correct 101 ms 7428 KB Output is correct
8 Correct 91 ms 7428 KB Output is correct
9 Correct 107 ms 7456 KB Output is correct
10 Correct 107 ms 7880 KB Output is correct
11 Execution timed out 1044 ms 6364 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 7876 KB Output is correct
2 Correct 134 ms 7760 KB Output is correct
3 Correct 168 ms 7704 KB Output is correct
4 Correct 138 ms 7780 KB Output is correct
5 Correct 144 ms 8208 KB Output is correct
6 Correct 43 ms 7528 KB Output is correct
7 Correct 56 ms 7584 KB Output is correct
8 Correct 56 ms 7600 KB Output is correct
9 Correct 76 ms 7720 KB Output is correct
10 Correct 58 ms 7480 KB Output is correct
11 Execution timed out 1036 ms 6752 KB Time limit exceeded
12 Halted 0 ms 0 KB -