oj.uz

Submission #526747

# Submission time Handle Problem Language Result Execution time Memory
526747 2022-02-16T03:45:34 Z joelau Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 1000 ms 14392 KB 
#include <bits/stdc++.h>
using namespace std;

int N,Q;
pair<int,int> lst[200005];
vector<int> A;
set< pair<int,int> > s;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> lst[i].first >> lst[i].second;
        A.push_back(lst[i].first); A.push_back(lst[i].second);
    }
    sort(A.begin(),A.end());
    A.resize(unique(A.begin(),A.end())-A.begin());
    for (int i = 0; i < N; ++i) {
        lst[i].first = lower_bound(A.begin(),A.end(),lst[i].first) - A.begin();
        lst[i].second = lower_bound(A.begin(),A.end(),lst[i].second) - A.begin();
    }
    cin >> Q;
    while (Q--) {
        int l,r; cin >> l >> r; l--, r--;
        s.clear();
        int ans = 1;
        for (int i = l; i <= r; ++i) {
            auto it = s.lower_bound(make_pair(lst[i].first,-1));
            bool can = true;
            if (it != s.end() && it->first <= lst[i].second) can = false;
            if (it != s.begin() && prev(it)->second >= lst[i].first) can = false;
            if (!can) {
                ans++;
                s.clear();
            }
            s.emplace(lst[i].first,lst[i].second).first;
        }
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3784 KB Output is correct
2 Correct 128 ms 3736 KB Output is correct
3 Correct 123 ms 3784 KB Output is correct
4 Correct 122 ms 3776 KB Output is correct
5 Correct 132 ms 3812 KB Output is correct
6 Correct 43 ms 3756 KB Output is correct
7 Correct 47 ms 3696 KB Output is correct
8 Correct 53 ms 3760 KB Output is correct
9 Correct 57 ms 3672 KB Output is correct
10 Correct 56 ms 3712 KB Output is correct
11 Correct 206 ms 12724 KB Output is correct
12 Correct 194 ms 12164 KB Output is correct
13 Correct 188 ms 11960 KB Output is correct
14 Correct 174 ms 6312 KB Output is correct
15 Correct 172 ms 6076 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 47 ms 3776 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 604 KB Output is correct
2 Correct 272 ms 708 KB Output is correct
3 Correct 267 ms 588 KB Output is correct
4 Correct 276 ms 588 KB Output is correct
5 Correct 287 ms 584 KB Output is correct
6 Correct 184 ms 604 KB Output is correct
7 Correct 263 ms 708 KB Output is correct
8 Correct 273 ms 596 KB Output is correct
9 Correct 320 ms 596 KB Output is correct
10 Correct 343 ms 600 KB Output is correct
11 Execution timed out 1037 ms 708 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 604 KB Output is correct
2 Correct 272 ms 708 KB Output is correct
3 Correct 267 ms 588 KB Output is correct
4 Correct 276 ms 588 KB Output is correct
5 Correct 287 ms 584 KB Output is correct
6 Correct 184 ms 604 KB Output is correct
7 Correct 263 ms 708 KB Output is correct
8 Correct 273 ms 596 KB Output is correct
9 Correct 320 ms 596 KB Output is correct
10 Correct 343 ms 600 KB Output is correct
11 Execution timed out 1037 ms 708 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 3832 KB Output is correct
2 Correct 333 ms 7224 KB Output is correct
3 Correct 360 ms 6856 KB Output is correct
4 Correct 313 ms 6716 KB Output is correct
5 Correct 331 ms 6944 KB Output is correct
6 Correct 167 ms 6864 KB Output is correct
7 Correct 253 ms 6736 KB Output is correct
8 Correct 255 ms 6736 KB Output is correct
9 Correct 274 ms 6764 KB Output is correct
10 Correct 356 ms 7096 KB Output is correct
11 Execution timed out 1069 ms 14392 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3784 KB Output is correct
2 Correct 128 ms 3736 KB Output is correct
3 Correct 123 ms 3784 KB Output is correct
4 Correct 122 ms 3776 KB Output is correct
5 Correct 132 ms 3812 KB Output is correct
6 Correct 43 ms 3756 KB Output is correct
7 Correct 47 ms 3696 KB Output is correct
8 Correct 53 ms 3760 KB Output is correct
9 Correct 57 ms 3672 KB Output is correct
10 Correct 56 ms 3712 KB Output is correct
11 Correct 206 ms 12724 KB Output is correct
12 Correct 194 ms 12164 KB Output is correct
13 Correct 188 ms 11960 KB Output is correct
14 Correct 174 ms 6312 KB Output is correct
15 Correct 172 ms 6076 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 47 ms 3776 KB Output is correct
18 Correct 295 ms 604 KB Output is correct
19 Correct 272 ms 708 KB Output is correct
20 Correct 267 ms 588 KB Output is correct
21 Correct 276 ms 588 KB Output is correct
22 Correct 287 ms 584 KB Output is correct
23 Correct 184 ms 604 KB Output is correct
24 Correct 263 ms 708 KB Output is correct
25 Correct 273 ms 596 KB Output is correct
26 Correct 320 ms 596 KB Output is correct
27 Correct 343 ms 600 KB Output is correct
28 Execution timed out 1037 ms 708 KB Time limit exceeded
29 Halted 0 ms 0 KB -