oj.uz

Submission #630198

# Submission time Handle Problem Language Result Execution time Memory
630198 2022-08-16T01:38:43 Z qwerasdfzxcl Radio Towers (IOI22_towers) C++17
17 / 100
 1144 ms 51372 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 (ans==0) return 1;
    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 Correct 290 ms 2896 KB Output is correct
2 Correct 959 ms 4560 KB Output is correct
3 Correct 768 ms 4528 KB Output is correct
4 Correct 736 ms 4544 KB Output is correct
5 Correct 793 ms 4516 KB Output is correct
6 Incorrect 894 ms 4560 KB 11314th lines differ - on the 1st token, expected: '1', found: '2'
7 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 862 ms 35748 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 335 ms 8156 KB Output is correct
2 Correct 875 ms 36024 KB Output is correct
3 Correct 1103 ms 36060 KB Output is correct
4 Correct 1144 ms 51280 KB Output is correct
5 Correct 994 ms 51188 KB Output is correct
6 Correct 1080 ms 51348 KB Output is correct
7 Correct 1020 ms 51264 KB Output is correct
8 Correct 621 ms 4556 KB Output is correct
9 Correct 833 ms 4560 KB Output is correct
10 Correct 886 ms 4516 KB Output is correct
11 Correct 871 ms 4652 KB Output is correct
12 Correct 116 ms 35924 KB Output is correct
13 Correct 186 ms 51188 KB Output is correct
14 Correct 184 ms 51220 KB Output is correct
15 Correct 13 ms 4560 KB Output is correct
16 Correct 13 ms 4520 KB Output is correct
17 Correct 120 ms 34696 KB Output is correct
18 Correct 121 ms 36060 KB Output is correct
19 Correct 122 ms 36124 KB Output is correct
20 Correct 183 ms 51264 KB Output is correct
21 Correct 188 ms 51372 KB Output is correct
22 Correct 179 ms 51232 KB Output is correct
23 Correct 177 ms 51192 KB Output is correct
24 Correct 13 ms 4528 KB Output is correct
25 Correct 13 ms 4524 KB Output is correct
26 Correct 13 ms 4536 KB Output is correct
27 Correct 19 ms 4520 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 Correct 290 ms 2896 KB Output is correct
2 Correct 959 ms 4560 KB Output is correct
3 Correct 768 ms 4528 KB Output is correct
4 Correct 736 ms 4544 KB Output is correct
5 Correct 793 ms 4516 KB Output is correct
6 Incorrect 894 ms 4560 KB 11314th lines differ - on the 1st token, expected: '1', found: '2'
7 Halted 0 ms 0 KB -