oj.uz

Submission #806591

# Submission time Handle Problem Language Result Execution time Memory
806591 2023-08-04T08:12:08 Z vjudge1 Event Hopping 2 (JOI21_event2) C++17
7 / 100
 167 ms 128580 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct node {
    int l, r, mx = 0;
    node *left = NULL, *right = NULL;

    node(int l, int r):l(l), r(r) {}
};

void check(node *x) {
    if(x->left == NULL) {
        x->left = new node(x->l, (x->l + x->r) / 2);
    }
    if(x->right == NULL) {
        x->right = new node((x->l + x->r) / 2, x->r);
    }
}

void update(int pos, int val, node *x) {
    if(x->l + 1 == x->r) {
        x->mx = val;
        return;
    }
    check(x);
    pos < x->left->r ?
    update(pos, val, x->left)  : 
    update(pos, val, x->right) ;
    x->mx = max(x->left->mx, x->right->mx);
}

int find(int r, node *x) {
    if(r <= x->l) {
        return x->mx;
    }
    check(x);
    int res = 0;
    if(x->left->r > r && x->left->mx) {
        res = find(r, x->left);
    }
    if(x->right->mx) {
        res = max(res, find(r, x->right));
    }
    return res;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    bool tsk = true;
    int n, k, mxr = -1;
    cin >> n >> k;
    vector < pair < int, int > > V(n);
    for(int i = 0; i < n; ++ i) {
        cin >> V[i].first >> V[i].second;
        tsk &= (!i || V[i - 1].first <= V[i].first);
        mxr = max(mxr, V[i].second);
    }

    if(tsk) {
        int t = 1;
        for(; t <= mxr; t <<= 1);
        node *root = new node(0, t);
        int dp[n + 10];
        for(int i = n; i --> 0;) {
            dp[i] = 1 + find(V[i].second, root); 
            update(V[i].first, dp[i], root);
        }
        if(root->mx < k) {
            cout << -1;
            return 0;
        }
        for(int i = 0, j = 0; i < n && k; ++ i) {
            if(j <= V[i].first && k <= dp[i]) {
                cout << i + 1 << '\n';
                -- k;
                j = V[i].second;
            }
        }
        return 0;
    }
   
    int t = 1;
    for(; t <= mxr; t <<= 1);
    node *root = new node(0, t);
    vector < int > pos(n);
    iota(pos.begin(), pos.end(), 0);
    sort(pos.rbegin(), pos.rend(), [&](int i, int j) {
                return V[i] < V[j];
            });
    
    int dp[n + 10];
    for(auto &i : pos) {
        dp[i] = 1 + find(V[i].second, root); 
        update(V[i].first, dp[i], root);
    }
    if(root->mx < k) {
        cout << -1;
        return 0;
    }
    bool use[n + 10] = {};
    set < int > st;
    for(int j = 0; k --> 0;) {
        for(int i = 0; i < n; ++ i) {
            if(!use[i] && j <= V[i].first && k < dp[i]) {
                use[i] = true;
                st.insert(i);
                j = V[i].second;
                break;
            }
        }
    }
    for(int i = 0; i < n && i < *st.rbegin(); ++ i) {
        if(st.find(i) != st.end()) {
            continue;
        }
        bool ok = true;
        for(auto &j : st) {
            if(V[i].second <= V[j].first || V[j].second <= V[i].first) {
                continue;
            }
            ok = false;
            break;
        }
        if(ok) {
            st.erase(prev(st.end()));
            st.insert(i);
        }
    }
    for(auto &i : st) {
        cout << i + 1 << '\n';
    }
}

Compilation message

event2.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 145 ms 128192 KB Output is correct
5 Correct 140 ms 127948 KB Output is correct
6 Correct 143 ms 127820 KB Output is correct
7 Correct 137 ms 127844 KB Output is correct
8 Correct 139 ms 127928 KB Output is correct
9 Correct 160 ms 127928 KB Output is correct
10 Correct 139 ms 127844 KB Output is correct
11 Correct 141 ms 127816 KB Output is correct
12 Correct 143 ms 127764 KB Output is correct
13 Correct 140 ms 127752 KB Output is correct
14 Correct 139 ms 127760 KB Output is correct
15 Correct 145 ms 127640 KB Output is correct
16 Correct 139 ms 127404 KB Output is correct
17 Correct 143 ms 127492 KB Output is correct
18 Correct 136 ms 127408 KB Output is correct
19 Correct 153 ms 127592 KB Output is correct
20 Correct 140 ms 127428 KB Output is correct
21 Correct 167 ms 127476 KB Output is correct
22 Correct 144 ms 127292 KB Output is correct
23 Correct 160 ms 127288 KB Output is correct
24 Correct 144 ms 127268 KB Output is correct
25 Correct 155 ms 125900 KB Output is correct
26 Correct 155 ms 125984 KB Output is correct
27 Correct 156 ms 125952 KB Output is correct
28 Correct 146 ms 127308 KB Output is correct
29 Correct 143 ms 127448 KB Output is correct
30 Correct 143 ms 127372 KB Output is correct
31 Correct 140 ms 127304 KB Output is correct
32 Correct 143 ms 127316 KB Output is correct
33 Correct 155 ms 126000 KB Output is correct
34 Correct 139 ms 127660 KB Output is correct
35 Correct 138 ms 127568 KB Output is correct
36 Correct 138 ms 127448 KB Output is correct
37 Correct 151 ms 128492 KB Output is correct
38 Correct 146 ms 128412 KB Output is correct
39 Correct 141 ms 128456 KB Output is correct
40 Correct 139 ms 128448 KB Output is correct
41 Correct 140 ms 128352 KB Output is correct
42 Correct 150 ms 128300 KB Output is correct
43 Correct 140 ms 128404 KB Output is correct
44 Correct 144 ms 128428 KB Output is correct
45 Correct 140 ms 128448 KB Output is correct
46 Correct 140 ms 128580 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 1 ms 320 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 145 ms 128192 KB Output is correct
5 Correct 140 ms 127948 KB Output is correct
6 Correct 143 ms 127820 KB Output is correct
7 Correct 137 ms 127844 KB Output is correct
8 Correct 139 ms 127928 KB Output is correct
9 Correct 160 ms 127928 KB Output is correct
10 Correct 139 ms 127844 KB Output is correct
11 Correct 141 ms 127816 KB Output is correct
12 Correct 143 ms 127764 KB Output is correct
13 Correct 140 ms 127752 KB Output is correct
14 Correct 139 ms 127760 KB Output is correct
15 Correct 145 ms 127640 KB Output is correct
16 Correct 139 ms 127404 KB Output is correct
17 Correct 143 ms 127492 KB Output is correct
18 Correct 136 ms 127408 KB Output is correct
19 Correct 153 ms 127592 KB Output is correct
20 Correct 140 ms 127428 KB Output is correct
21 Correct 167 ms 127476 KB Output is correct
22 Correct 144 ms 127292 KB Output is correct
23 Correct 160 ms 127288 KB Output is correct
24 Correct 144 ms 127268 KB Output is correct
25 Correct 155 ms 125900 KB Output is correct
26 Correct 155 ms 125984 KB Output is correct
27 Correct 156 ms 125952 KB Output is correct
28 Correct 146 ms 127308 KB Output is correct
29 Correct 143 ms 127448 KB Output is correct
30 Correct 143 ms 127372 KB Output is correct
31 Correct 140 ms 127304 KB Output is correct
32 Correct 143 ms 127316 KB Output is correct
33 Correct 155 ms 126000 KB Output is correct
34 Correct 139 ms 127660 KB Output is correct
35 Correct 138 ms 127568 KB Output is correct
36 Correct 138 ms 127448 KB Output is correct
37 Correct 151 ms 128492 KB Output is correct
38 Correct 146 ms 128412 KB Output is correct
39 Correct 141 ms 128456 KB Output is correct
40 Correct 139 ms 128448 KB Output is correct
41 Correct 140 ms 128352 KB Output is correct
42 Correct 150 ms 128300 KB Output is correct
43 Correct 140 ms 128404 KB Output is correct
44 Correct 144 ms 128428 KB Output is correct
45 Correct 140 ms 128448 KB Output is correct
46 Correct 140 ms 128580 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 0 ms 324 KB Output is correct
53 Correct 0 ms 340 KB Output is correct
54 Incorrect 1 ms 320 KB Output isn't correct
55 Halted 0 ms 0 KB -