Submission #674968

#	Time	Username	Problem	Language	Result	Execution time	Memory
674968		vjudge1	Osumnjičeni (COCI21_osumnjiceni)	C++17	10 / 110	140 ms	18832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
 
#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define int long long
#define ld long double
const int INF = 1e18;
const int inf = 1e9;

const int N = 2e5+10, LOG = 20;
int l[N], r[N];
int st[N][LOG];
set<pi> s;
 
bool fit(int ix){
    if(s.empty()) return 1;

    auto it = s.lower_bound({l[ix], 0});
    pi c = (it == s.end() ? make_pair(INF, INF) : *it), p = (it == s.begin() ? make_pair(-INF, -INF) : *prev(it));

    if(r[ix] >= c.F || p.S >= l[ix]) return 0;
    return 1;
}

void solve(){
    int n; cin >> n;
    for(int i=0; i<n; i++)
        cin >> l[i] >> r[i];

    int trash; cin >> trash >> trash >> trash;
    
    int ans = 1;
    for(int i=0; i<n; i++)
        if(fit(i)) s.insert({l[i], r[i]});
        else {
            s.clear();
            s.insert({l[i], r[i]});
            ans++;
        }
    cout << ans << "\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
 
    int tt = 1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

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