oj.uz

Submission #630197

# Submission time Handle Problem Language Result Execution time Memory
630197 2022-08-16T01:34:33 Z qwerasdfzxcl Radio Towers (IOI22_towers) C++17
17 / 100
 1170 ms 51296 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, a[100100], b[100100], typ[100100];
vector<int> T;

struct Node{
    int x, l, r;
    Node(){}
    Node(int _x, int _l, int _r): x(_x), l(_l), r(_r) {}
};
struct PST{
    Node tree[4004000];
    int root[100100], pt1, pt2, sz;
    void init(int n){
        sz = n;
        tree[0] = Node(0, -1, -1);
        root[0] = 0;
        pt1 = 1, pt2 = 1;
    }
    void add(){
        tree[pt1] = tree[root[pt2-1]];
        root[pt2] = pt1;
        ++pt1, ++pt2;
    }
    int _new(int i){
        if (i!=-1) tree[pt1++] = tree[i];
        else tree[pt1++] = Node(0, -1, -1);
        return pt1-1;
    }
    void build(int i, int l, int r, int a[]){
        if (l==r) {tree[i].x = a[l]; return;}
        int m = (l+r)>>1;

        tree[i].l = _new(tree[i].l);
        tree[i].r = _new(tree[i].r);
        build(tree[i].l, l, m, a); build(tree[i].r, m+1, r, a);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
    }
    void update(int i, int l, int r, int s, int x){
        if (r<s || s<l) return;
        if (l==r) {tree[i].x = x; return;}
        int m = (l+r)>>1;

        tree[i].l = _new(tree[i].l);
        tree[i].r = _new(tree[i].r);
        update(tree[i].l, l, m, s, x); update(tree[i].r, m+1, r, s, x);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
    }
    int query(int i, int l, int r, int s, int e){
        if (i==-1) return 0;
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }
    int left_bound(int i, int l, int r, int s, int e){
        if (r<s || e<l) return -1;
        if (tree[i].x==0) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = left_bound(tree[i].l, l, m, s, e);
        if (tmp!=-1) return tmp;
        return left_bound(tree[i].r, m+1, r, s, e);
    }
    int right_bound(int i, int l, int r, int s, int e){
        if (r<s || e<l) return -1;
        if (tree[i].x==0) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = right_bound(tree[i].r, m+1, r, s, e);
        if (tmp!=-1) return tmp;
        return right_bound(tree[i].l, l, m, s, e);
    }

    void update(int s, int x){
        update(root[pt2-1], 1, sz, s, x);
    }
    int query(int t, int l, int r){
        return query(root[t], 1, sz, l, r);
    }
    int left_bound(int t, int l, int r){
        return left_bound(root[t], 1, sz, l, r);
    }
    int right_bound(int t, int l, int r){
        return right_bound(root[t], 1, sz, l, r);
    }
}tree1;

struct Seg{
    int tree[200200], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    int query(int l, int r){
        ++r;
        int ret = 1e9;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}tree2;

set<int> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int myabs(int x){
    if (x<0) return -x;
    return x;
}

int getd(int x){
    auto iter = st.find(x);
    if (iter==st.end() || next(iter)==st.end()) return -1;
    return myabs(a[*next(iter)] - a[*iter]);
}

void init(int N, std::vector<int> H) {
    n = N;
    for (int i=1;i<=n;i++) a[i] = H[i-1];

    int tl = 1, tr = n;
    for (;tl<n;tl++) if (a[tl] < a[tl+1]) break;
    for (;tr>1;tr--) if (a[tr-1] > a[tr]) break;
    assert(tl<=tr);

    st.insert(tl);
    st.insert(tr);
    b[tl] = b[tr] = 1;
    typ[tl] = typ[tr] = -1;
    for (int i=tl+1;i<tr;i++){
        if (a[i-1] < a[i] && a[i] > a[i+1]){
            b[i] = 1, typ[i] = 1;
            st.insert(i);
        }
        if (a[i-1] > a[i] && a[i] < a[i+1]){
            b[i] = 1, typ[i] = -1;
            st.insert(i);
        }
    }

    for (auto iter=st.begin();next(iter)!=st.end();iter++) pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);

    tree1.init(n);
    tree1.build(0, 1, n, b);
    tree2.init(n+1);
    T.push_back(0);

    while(!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if (getd(i)!=d) continue;

        auto iter = st.find(i);
        T.push_back(d);
        tree1.add();
        tree1.update(i, 0);
        tree1.update(*next(iter), 0);
        iter = st.erase(iter, next(next(iter)));

        //for (auto &x:st) printf(" %d", x);
        //printf("\n");

        if (iter==st.begin() || iter==st.end()) continue;
        //printf(" add: %d %d -> %d\n", *prev(iter), *iter, getd(*prev(iter)));
        --iter;
        pq.emplace(myabs(a[*next(iter)] - a[*iter]), *iter);
    }

    /*for (int i=1;i<=n;i++) printf("%d ", b[i]);
    printf("\n");
    for (int i=1;i<=n;i++) printf("%d ", typ[i]);
    printf("\n");
    for (auto &x:T) printf("%d ", x);
    printf("\n");*/

    //printf("%d\n", tree1.tree[0].x);
}

int max_towers(int l, int r, int D) {
    ++l, ++r;
    int t = lower_bound(T.begin(), T.end(), D) - T.begin() - 1;
    int ans = tree1.query(t, l, r);
    //printf("%d -> ", ans);
    if (ans==0) return 1;

    int L = tree1.left_bound(t, l, r), R = tree1.right_bound(t, l, r);
    assert(L!=-1);
    assert(R!=-1);

    if (typ[L]==1){
        int tmp = tree2.query(l, L-1);
        if (myabs(a[L] - tmp) >= D) ans++;
        else ans--;
    }
    if (typ[R]==1){
        int tmp  = tree2.query(R+1, r);
        if (myabs(a[R] - tmp) >= D) ans++;
        else ans--;
    }

    assert(ans%2==1);
    return (ans+1)/2;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5192 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 765 ms 35680 KB 1st lines differ - on the 1st token, expected: '11903', found: '11904'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 8160 KB Output is correct
2 Correct 851 ms 36084 KB Output is correct
3 Correct 1061 ms 36048 KB Output is correct
4 Correct 1158 ms 51264 KB Output is correct
5 Correct 1170 ms 51236 KB Output is correct
6 Correct 1163 ms 51296 KB Output is correct
7 Correct 1095 ms 51232 KB Output is correct
8 Correct 876 ms 4528 KB Output is correct
9 Correct 814 ms 4580 KB Output is correct
10 Correct 891 ms 4560 KB Output is correct
11 Correct 817 ms 4560 KB Output is correct
12 Correct 113 ms 36040 KB Output is correct
13 Correct 189 ms 51244 KB Output is correct
14 Correct 186 ms 51228 KB Output is correct
15 Correct 12 ms 4552 KB Output is correct
16 Correct 18 ms 4516 KB Output is correct
17 Correct 116 ms 34628 KB Output is correct
18 Correct 127 ms 35988 KB Output is correct
19 Correct 125 ms 36116 KB Output is correct
20 Correct 185 ms 51228 KB Output is correct
21 Correct 181 ms 51264 KB Output is correct
22 Correct 191 ms 51244 KB Output is correct
23 Correct 177 ms 51264 KB Output is correct
24 Correct 16 ms 4504 KB Output is correct
25 Correct 13 ms 4516 KB Output is correct
26 Correct 12 ms 4656 KB Output is correct
27 Correct 16 ms 4532 KB Output is correct
28 Correct 2 ms 848 KB Output is correct
29 Correct 2 ms 976 KB Output is correct
30 Correct 2 ms 976 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 2 ms 848 KB Output is correct
35 Correct 2 ms 848 KB Output is correct
36 Correct 2 ms 976 KB Output is correct
37 Correct 2 ms 976 KB Output is correct
38 Correct 2 ms 976 KB Output is correct
39 Correct 2 ms 976 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 1 ms 336 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '13', found: '14'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5192 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -