oj.uz

Submission #414898

# Submission time Handle Problem Language Result Execution time Memory
414898 2021-05-31T10:27:37 Z 반딧불(#7587) Event Hopping 2 (JOI21_event2) C++17
7 / 100
 3000 ms 29864 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int l, r, idx;
    dat(){}
    dat(int l, int r, int idx): l(l), r(r), idx(idx){}
};

struct Range{
    int l, r, val;
    Range(){}
    Range(int l, int r, int val): l(l), r(r), val(val){}

    bool operator<(const Range &nxt)const{
        if(l != nxt.l) return l<nxt.l;
        return val < nxt.val;
    }
};

struct segmentTree{
    int tree[800002], lazy[800002];

    void init(int i, int l, int r){
        tree[i] = lazy[i] = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        tree[i] = lazy[i];
        if(l!=r) lazy[i*2] = lazy[i*2+1] = lazy[i];
        lazy[i] = 0;
    }

    int getVal(int i, int l, int r, int idx){
        propagate(i, l, r);
        if(l==r) return tree[i];
        int m = (l+r)>>1;
        if(idx <= m) return getVal(i*2, l, m, idx);
        return getVal(i*2+1, m+1, r, idx);
    }

    void rangeUpdate(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        rangeUpdate(i*2, l, m, s, e, val);
        rangeUpdate(i*2+1, m+1, r, s, e, val);
    }
} tree;

int n, m, k;
dat arr[100002];

int lSparse[100002][20], rSparse[100002][20];
vector<int> ans;
int sum;
set<Range> st;

void renumber(){
    vector<int> vec;
    for(int i=1; i<=n; i++) vec.push_back(arr[i].l), vec.push_back(arr[i].r);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    m = (int)vec.size();
    for(int i=1; i<=n; i++){
        arr[i].l = lower_bound(vec.begin(), vec.end(), arr[i].l) - vec.begin() + 1;
        arr[i].r = lower_bound(vec.begin(), vec.end(), arr[i].r) - vec.begin() + 1;
    }
}

void makeSparse(){
    vector<dat> vec (arr+1, arr+n+1);

    tree.init(1, 1, m);
    sort(vec.begin(), vec.end(), [&](dat x, dat y){
        return x.l < y.l;
    });
    for(auto p: vec){
        lSparse[p.idx][0] = tree.getVal(1, 1, m, p.l);
        tree.rangeUpdate(1, 1, m, p.r, m, p.idx);
    }

    tree.init(1, 1, m);
    sort(vec.begin(), vec.end(), [&](dat x, dat y){
        return x.r > y.r;
    });
    for(auto p: vec){
        rSparse[p.idx][0] = tree.getVal(1, 1, m, p.r);
        tree.rangeUpdate(1, 1, m, 1, p.l, p.idx);
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].l, &arr[i].r);
        arr[i].idx = i;
    }

    renumber();
    makeSparse();

    for(int d=1; d<20; d++){
        for(int i=1; i<=n; i++){
            lSparse[i][d] = lSparse[lSparse[i][d-1]][d-1];
            rSparse[i][d] = rSparse[rSparse[i][d-1]][d-1];
        }
    }

    int maxAble = 0;
    for(int i=1; i<=n; i++){
        int dCnt = 1;
        for(int d=19; d>=0; d--){
            if(rSparse[i][d]){
                dCnt += (1<<d);
                i = rSparse[i][d];
            }
        }
        maxAble = max(maxAble, dCnt);
    }

    st.insert(Range(1, m, maxAble));
    sum = maxAble;
    for(int i=1; i<=n; i++){
        auto it = st.lower_bound(Range(arr[i].l, 0, 1e9));
        if(it == st.begin()) continue;
        --it;
        if(!(it->l <= arr[i].l && arr[i].r <= it->r)) continue;

        int lVal = 0, rVal = 0, tmp = i;
        for(int d=19; d>=0; d--){
            if(!lSparse[tmp][d] || arr[lSparse[tmp][d]].l < it->l) continue;
            lVal += (1<<d);
            tmp = lSparse[tmp][d];
        }
        tmp = i;
        for(int d=19; d>=0; d--){
            if(!rSparse[tmp][d] || arr[rSparse[tmp][d]].r > it->r) continue;
            rVal += (1<<d);
            tmp = rSparse[tmp][d];
        }

        if(sum - it->val + (lVal + rVal + 1) < k) continue;
        ans.push_back(i);

        int tL = it->l, tR = it->r;
        sum -= it->val;
        sum += lVal + rVal + 1;
        st.erase(it);

        st.insert(Range(tL, arr[i].l, lVal));
        st.insert(Range(arr[i].r, tR, rVal));
    }

    if((int)ans.size() < k) printf("-1");
    else{
        for(int i=0; i<k; i++) printf("%d\n", ans[i]);
    }
}

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
event2.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         scanf("%d %d", &arr[i].l, &arr[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 239 ms 29832 KB Output is correct
5 Correct 219 ms 29756 KB Output is correct
6 Correct 217 ms 29864 KB Output is correct
7 Correct 231 ms 29728 KB Output is correct
8 Correct 217 ms 29800 KB Output is correct
9 Correct 230 ms 29820 KB Output is correct
10 Correct 217 ms 29784 KB Output is correct
11 Correct 224 ms 29708 KB Output is correct
12 Correct 204 ms 27480 KB Output is correct
13 Correct 195 ms 27216 KB Output is correct
14 Correct 205 ms 27264 KB Output is correct
15 Correct 194 ms 27124 KB Output is correct
16 Correct 161 ms 24336 KB Output is correct
17 Correct 161 ms 24400 KB Output is correct
18 Correct 163 ms 24456 KB Output is correct
19 Correct 153 ms 24400 KB Output is correct
20 Correct 171 ms 24384 KB Output is correct
21 Correct 155 ms 24344 KB Output is correct
22 Correct 163 ms 24404 KB Output is correct
23 Correct 166 ms 24472 KB Output is correct
24 Correct 180 ms 24428 KB Output is correct
25 Correct 170 ms 24628 KB Output is correct
26 Correct 172 ms 24420 KB Output is correct
27 Correct 178 ms 24432 KB Output is correct
28 Correct 154 ms 24384 KB Output is correct
29 Correct 156 ms 24348 KB Output is correct
30 Correct 182 ms 24384 KB Output is correct
31 Correct 158 ms 24424 KB Output is correct
32 Correct 169 ms 24524 KB Output is correct
33 Correct 213 ms 24404 KB Output is correct
34 Correct 193 ms 27244 KB Output is correct
35 Correct 206 ms 27040 KB Output is correct
36 Correct 190 ms 26996 KB Output is correct
37 Correct 187 ms 26836 KB Output is correct
38 Correct 188 ms 26732 KB Output is correct
39 Correct 184 ms 26748 KB Output is correct
40 Correct 185 ms 26656 KB Output is correct
41 Correct 188 ms 26656 KB Output is correct
42 Correct 167 ms 24352 KB Output is correct
43 Correct 205 ms 26520 KB Output is correct
44 Correct 249 ms 26428 KB Output is correct
45 Correct 194 ms 26276 KB Output is correct
46 Correct 200 ms 26168 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Execution timed out 3066 ms 332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Execution timed out 3066 ms 332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 239 ms 29832 KB Output is correct
5 Correct 219 ms 29756 KB Output is correct
6 Correct 217 ms 29864 KB Output is correct
7 Correct 231 ms 29728 KB Output is correct
8 Correct 217 ms 29800 KB Output is correct
9 Correct 230 ms 29820 KB Output is correct
10 Correct 217 ms 29784 KB Output is correct
11 Correct 224 ms 29708 KB Output is correct
12 Correct 204 ms 27480 KB Output is correct
13 Correct 195 ms 27216 KB Output is correct
14 Correct 205 ms 27264 KB Output is correct
15 Correct 194 ms 27124 KB Output is correct
16 Correct 161 ms 24336 KB Output is correct
17 Correct 161 ms 24400 KB Output is correct
18 Correct 163 ms 24456 KB Output is correct
19 Correct 153 ms 24400 KB Output is correct
20 Correct 171 ms 24384 KB Output is correct
21 Correct 155 ms 24344 KB Output is correct
22 Correct 163 ms 24404 KB Output is correct
23 Correct 166 ms 24472 KB Output is correct
24 Correct 180 ms 24428 KB Output is correct
25 Correct 170 ms 24628 KB Output is correct
26 Correct 172 ms 24420 KB Output is correct
27 Correct 178 ms 24432 KB Output is correct
28 Correct 154 ms 24384 KB Output is correct
29 Correct 156 ms 24348 KB Output is correct
30 Correct 182 ms 24384 KB Output is correct
31 Correct 158 ms 24424 KB Output is correct
32 Correct 169 ms 24524 KB Output is correct
33 Correct 213 ms 24404 KB Output is correct
34 Correct 193 ms 27244 KB Output is correct
35 Correct 206 ms 27040 KB Output is correct
36 Correct 190 ms 26996 KB Output is correct
37 Correct 187 ms 26836 KB Output is correct
38 Correct 188 ms 26732 KB Output is correct
39 Correct 184 ms 26748 KB Output is correct
40 Correct 185 ms 26656 KB Output is correct
41 Correct 188 ms 26656 KB Output is correct
42 Correct 167 ms 24352 KB Output is correct
43 Correct 205 ms 26520 KB Output is correct
44 Correct 249 ms 26428 KB Output is correct
45 Correct 194 ms 26276 KB Output is correct
46 Correct 200 ms 26168 KB Output is correct
47 Correct 1 ms 332 KB Output is correct
48 Correct 1 ms 332 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Execution timed out 3066 ms 332 KB Time limit exceeded
51 Halted 0 ms 0 KB -