oj.uz

Submission #674968

# Submission time Handle Problem Language Result Execution time Memory
674968 2022-12-26T17:44:23 Z vjudge1 Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 140 ms 18832 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6984 KB Output is correct
2 Correct 45 ms 6940 KB Output is correct
3 Correct 43 ms 6932 KB Output is correct
4 Correct 43 ms 7116 KB Output is correct
5 Correct 44 ms 7268 KB Output is correct
6 Correct 41 ms 6604 KB Output is correct
7 Correct 42 ms 6724 KB Output is correct
8 Correct 46 ms 6804 KB Output is correct
9 Correct 44 ms 6892 KB Output is correct
10 Correct 44 ms 6596 KB Output is correct
11 Correct 140 ms 18832 KB Output is correct
12 Correct 130 ms 17612 KB Output is correct
13 Correct 130 ms 17736 KB Output is correct
14 Correct 104 ms 10260 KB Output is correct
15 Correct 98 ms 9932 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 41 ms 7128 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6984 KB Output is correct
2 Correct 45 ms 6940 KB Output is correct
3 Correct 43 ms 6932 KB Output is correct
4 Correct 43 ms 7116 KB Output is correct
5 Correct 44 ms 7268 KB Output is correct
6 Correct 41 ms 6604 KB Output is correct
7 Correct 42 ms 6724 KB Output is correct
8 Correct 46 ms 6804 KB Output is correct
9 Correct 44 ms 6892 KB Output is correct
10 Correct 44 ms 6596 KB Output is correct
11 Correct 140 ms 18832 KB Output is correct
12 Correct 130 ms 17612 KB Output is correct
13 Correct 130 ms 17736 KB Output is correct
14 Correct 104 ms 10260 KB Output is correct
15 Correct 98 ms 9932 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 41 ms 7128 KB Output is correct
18 Incorrect 1 ms 468 KB Output isn't correct
19 Halted 0 ms 0 KB -