109222024-04-19 11:20:43k_balintFőnökszámcpp17Accepted 100/100239ms23512 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;
    bool ok = 1;
    while(ok){
        ok = 0;
        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) ok=1,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
1Accepted3ms1888 KiB
2Accepted37ms2252 KiB
subtask25/5
3Accepted3ms2292 KiB
4Accepted3ms2376 KiB
5Accepted3ms2512 KiB
6Accepted4ms2728 KiB
subtask310/10
7Accepted3ms2692 KiB
8Accepted3ms2696 KiB
9Accepted3ms2704 KiB
10Accepted3ms2692 KiB
11Accepted3ms2688 KiB
12Accepted3ms2928 KiB
13Accepted4ms3012 KiB
14Accepted4ms3168 KiB
subtask410/10
15Accepted3ms3240 KiB
16Accepted3ms3476 KiB
17Accepted3ms3712 KiB
18Accepted3ms3764 KiB
19Accepted4ms3860 KiB
20Accepted8ms3844 KiB
21Accepted8ms4076 KiB
22Accepted75ms13368 KiB
subtask525/25
23Accepted3ms3956 KiB
24Accepted3ms4088 KiB
25Accepted4ms4300 KiB
26Accepted4ms4388 KiB
27Accepted18ms4468 KiB
28Accepted28ms4720 KiB
29Accepted35ms4684 KiB
30Accepted35ms4644 KiB
subtask650/50
31Accepted3ms4592 KiB
32Accepted37ms4640 KiB
33Accepted3ms2292 KiB
34Accepted3ms2376 KiB
35Accepted3ms2512 KiB
36Accepted4ms2728 KiB
37Accepted3ms2692 KiB
38Accepted3ms2696 KiB
39Accepted3ms2704 KiB
40Accepted3ms2692 KiB
41Accepted3ms2688 KiB
42Accepted3ms2928 KiB
43Accepted4ms3012 KiB
44Accepted4ms3168 KiB
45Accepted3ms3240 KiB
46Accepted3ms3476 KiB
47Accepted3ms3712 KiB
48Accepted3ms3764 KiB
49Accepted4ms3860 KiB
50Accepted8ms3844 KiB
51Accepted8ms4076 KiB
52Accepted75ms13368 KiB
53Accepted3ms3956 KiB
54Accepted3ms4088 KiB
55Accepted4ms4300 KiB
56Accepted4ms4388 KiB
57Accepted18ms4468 KiB
58Accepted28ms4720 KiB
59Accepted35ms4684 KiB
60Accepted35ms4644 KiB
61Accepted4ms4596 KiB
62Accepted4ms4752 KiB
63Accepted4ms4600 KiB
64Accepted37ms9304 KiB
65Accepted4ms4596 KiB
66Accepted4ms4612 KiB
67Accepted4ms4688 KiB
68Accepted4ms4816 KiB
69Accepted35ms4868 KiB
70Accepted239ms23512 KiB