Submission #528467

# Submission time Handle Problem Language Result Execution time Memory
528467 2022-02-20T10:42:56 Z Slavita Osumnjičeni (COCI21_osumnjiceni) C++14
0 / 110
124 ms 7312 KB
#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;
}
/*
*/
# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 6976 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 7312 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 6976 KB Output isn't correct
2 Halted 0 ms 0 KB -