109212024-04-19 11:17:13k_balintFőnökszámcpp17Time limit exceeded 50/100476ms13456 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
multiset<pair<int,int>> s;

void ins(int a, int b){
    auto it = s.lower_bound(make_pair(a+1,-1));
    if(it != s.end()){
        it = s.lower_bound(make_pair(it->first+1,-1));
        if(it != s.begin()) --it;
        if(it->first > a && it->second > b) return;
    }

    s.insert(make_pair(a,b));
    int k = a;
    while(1){
        it = s.lower_bound(make_pair(k,-1));
        if(it == s.begin()) break;
        --it;
        k = it->first;
        it = s.lower_bound(make_pair(k,-1));
        while(it != s.end() && it->first < a && it->second < b) it = s.erase(it);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        ins(a,b);
        cout << s.size() << '\n';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2016 KiB
2Accepted35ms2324 KiB
subtask25/5
3Accepted3ms2448 KiB
4Accepted3ms2784 KiB
5Accepted3ms2936 KiB
6Accepted4ms2964 KiB
subtask310/10
7Accepted3ms2952 KiB
8Accepted3ms3196 KiB
9Accepted4ms3292 KiB
10Accepted3ms3364 KiB
11Accepted3ms3436 KiB
12Accepted3ms3464 KiB
13Accepted4ms3696 KiB
14Accepted4ms3908 KiB
subtask410/10
15Accepted3ms3864 KiB
16Accepted3ms3840 KiB
17Accepted3ms3848 KiB
18Accepted3ms3852 KiB
19Accepted4ms4060 KiB
20Accepted8ms3944 KiB
21Accepted8ms4136 KiB
22Accepted72ms13456 KiB
subtask525/25
23Accepted3ms4152 KiB
24Accepted3ms4168 KiB
25Accepted3ms4076 KiB
26Accepted4ms4072 KiB
27Accepted17ms4196 KiB
28Accepted28ms4348 KiB
29Accepted32ms4448 KiB
30Accepted34ms4440 KiB
subtask60/50
31Accepted3ms4400 KiB
32Accepted35ms4556 KiB
33Accepted3ms2448 KiB
34Accepted3ms2784 KiB
35Accepted3ms2936 KiB
36Accepted4ms2964 KiB
37Accepted3ms2952 KiB
38Accepted3ms3196 KiB
39Accepted4ms3292 KiB
40Accepted3ms3364 KiB
41Accepted3ms3436 KiB
42Accepted3ms3464 KiB
43Accepted4ms3696 KiB
44Accepted4ms3908 KiB
45Accepted3ms3864 KiB
46Accepted3ms3840 KiB
47Accepted3ms3848 KiB
48Accepted3ms3852 KiB
49Accepted4ms4060 KiB
50Accepted8ms3944 KiB
51Accepted8ms4136 KiB
52Accepted72ms13456 KiB
53Accepted3ms4152 KiB
54Accepted3ms4168 KiB
55Accepted3ms4076 KiB
56Accepted4ms4072 KiB
57Accepted17ms4196 KiB
58Accepted28ms4348 KiB
59Accepted32ms4448 KiB
60Accepted34ms4440 KiB
61Accepted4ms4412 KiB
62Accepted6ms4492 KiB
63Accepted4ms4416 KiB
64Accepted35ms9116 KiB
65Accepted4ms4416 KiB
66Accepted4ms4408 KiB
67Accepted4ms4408 KiB
68Accepted4ms4408 KiB
69Accepted35ms4540 KiB
70Time limit exceeded476ms4616 KiB