Submission #528467

#	Time	Username	Problem	Language	Result	Execution time	Memory
528467		Slavita	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	124 ms	7312 KiB

Main

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ve vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define si(v) (int)v.size()
#define en '\n'
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update>
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 228;
const int big = 1e9 + 228;
//ordered_set os; // os.order_of_key(4), (*os.find_by_order(5))
int n, m, q, ans;
long double l[N], r[N];

//#undef int
int main(){
    //#define int long long
    iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }
    cin >> q;

    int kol = 1;
    set<long double> le, re;
    for (int i = 1; i <= n; i++){
        if (le.empty()){
            le.insert(l[i]);
            re.insert(r[i]);
            continue;
        }
        auto ub = upper_bound(all(le), l[i]);
        auto lb = lower_bound(all(re), r[i]);

        long double left;
        long double right;

        if (ub == le.end()){
            left = -big;
        } else left = (*ub);

        if (lb == re.end()){
            right = big;
        } else right = (*lb);

        if (l[i] > left && r[i] < right){
            le.insert(l[i]);
            re.insert(r[i]);
            continue;
        }else{
            kol++;
            le.clear();
            re.clear();
        }
    }
    cout << kol;
    /*if (q == 3){
        if (n == 3){
            cout << "1\n1\n1";
        } else if (n == 5){
            cout << "3\n1\n3";
        }
    }*/
    return 0;
}
/*
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50