oj.uz

Submission #1040994

# Submission time Handle Problem Language Result Execution time Memory
1040994 2024-08-01T13:39:33 Z _8_8_ Radio Towers (IOI22_towers) C++17
21 / 100
 787 ms 335860 KB 
#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
int n,pos;
vector<int> h;
const int N = 2e5 + 12,B = 20;
int sp[20][N],p[20][N],lg[N],sp1[20][N],p1[20][N];
bool sub = false;
void build() {
    for(int i = 0;i < n;i++){
        sp1[0][i] = sp[0][i] = h[i];
        p1[0][i] = p[0][i] = i;
    }
    for(int i = 1;i < B;i++) {
        for(int j = 0;j + (1 << i) - 1 < n;j++) {
            int X = sp[i - 1][j],Y = sp[i - 1][j + (1 << (i - 1))];
            sp[i][j] = min(X,Y);
            if(sp[i][j] == X) {
                p[i][j] = p[i - 1][j];
            }else {
                p[i][j] = p[i - 1][j + (1 << (i - 1))];
            }
            X = sp1[i - 1][j],Y = sp1[i - 1][j + (1 << (i - 1))];
            sp1[i][j] = max(X,Y);
            if(sp1[i][j] == X) {
                p1[i][j] = p1[i - 1][j];
            }else {
                p1[i][j] = p1[i - 1][j + (1 << (i - 1))];
            }
        }
    }
}
pair<int,int> get(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp[i][L],p[i][L]);
    pair<int,int> y = make_pair(sp[i][R - (1 << i) + 1],p[i][R - (1 << i) + 1]);
    return min(x,y);
}
pair<int,int> get1(int L,int R) {
    int i = lg[R - L + 1];
    pair<int,int> x = make_pair(sp1[i][L],p1[i][L]);
    pair<int,int> y = make_pair(sp1[i][R - (1 << i) + 1],p1[i][R - (1 << i) + 1]);
    return max(x,y);
}
int _l[N],_r[N],val[N],_mx[N],_mn[N];
vector<int> b,t;
struct node {
    bool e = true;
    int mx = 0,mn = 1e9,ans = 0,ans1 = 0;
}T[N * 4];
node merge(node l,node r) {
    if(l.e) return r;
    if(r.e) return l;
    node ret;
    ret.e = false;
    ret.mx = max(l.mx,r.mx);
    ret.mn = min(l.mn,r.mn);
    ret.ans = max({l.ans,r.ans,l.mx - r.mn});
    ret.ans1 = max({l.ans1,r.ans1,r.mx - l.mn});
    return ret;
}
void build_(int v = 1,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        T[v].mx = T[v].mn = h[tl];
        T[v].e = false;
    }else {
        int tm = (tl + tr) >> 1;
        build_(v + v,tl,tm);
        build_(v + v + 1,tm + 1,tr);
        T[v] = merge(T[v + v],T[v + v + 1]);
    }
}
node Get(int l,int r,int v = 1,int tl = 0,int tr = n - 1) {

    if(l > r || tl > r || l > tr) {
        node f;return f;
    }
    if(tl >= l && tr <= r) return T[v];
    int tm = (tl + tr) >> 1;
    return merge(Get(l,r,v+v,tl,tm),Get(l,r,v+v+1,tm+1,tr));
}

struct Node{
    Node *l = 0,*r = 0;
    int mx = 0,mn = (int)1e9,s = 0;
    Node (){}
    Node (int val) {
        mx= mn = val;
        s = 1;
    }
    Node (Node *l_,Node *r_) {
        l = l_;
        r = r_;
        mx = max(l->mx,r->mx);
        mn = min(l->mn,r->mn);
        s = l->s + r->s;
    }
};
using pnode = Node *;
pnode t_[N];
pnode build1(int tl = 0,int tr = n - 1) {
    if(tl == tr) return new Node();
    int tm = (tl + tr) >> 1;
    return new Node(build1(tl,tm),build1(tm + 1,tr));
}
pnode upd(pnode v,int pos,int tl = 0,int tr = n - 1) {
    if(tl == tr) {
        return new Node(tl);
    } else {
        int tm = (tl + tr) >> 1;
        if(pos <= tm) {
            return new Node(upd(v->l,pos,tl,tm),v->r);
        } 
        return new Node(v->l,upd(v->r,pos,tm+1,tr));
    }
}
int get_sum(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->s;
    }else {
        int tm = (tl + tr) >> 1;
        return get_sum(l,r,v->l,tl,tm) + get_sum(l,r,v->r,tm+1,tr);
    }
}
int get_mx(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return v->mx;
    }else {
        int tm = (tl + tr) >> 1;
        return max(get_mx(l,r,v->l,tl,tm),get_mx(l,r,v->r,tm+1,tr));
    }
}
int get_mn(int l,int r,pnode v,int tl = 0,int tr = n - 1) {
    if(l > r || tl > r || l > tr) return (int)1e9;
    if(tl >= l && tr <= r) {
        return v->mn;
    }else {
        int tm = (tl + tr) >> 1;
        return min(get_mn(l,r,v->l,tl,tm),get_mn(l,r,v->r,tm+1,tr));
    }
}
void init(int nn, vector<int> H) {
    n = nn;
    h = H;
    build();
    build_();
    for(int i = 2;i <= n;i++) {
        lg[i] = lg[i / 2] + 1;
    }
    vector<int> st;
    for(int i = 0;i < n;i++) {
        while((int)st.size() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _l[i] = (st.empty() ? -1 : st.back());
        st.push_back(i);
    }
    st.clear();
    for(int i = n - 1;i >= 0;i--) {
        while(!st.empty() && h[st.back()] > h[i]) {
            st.pop_back();
        }
        _r[i] = (st.empty() ? n : st.back());
        st.push_back(i);
    }
    for(int i = 0;i < n;i++) {
        val[i] = min(get1(_l[i] + 1,i).first,get1(i,_r[i]-1).first) - h[i];
        t.push_back(i);
    }
    sort(t.begin(),t.end(),[&](int x,int y){
        return val[x] < val[y];
    });
    for(int i:t) {
        b.push_back(val[i]);
    }
    _mx[n - 1] = _mn[n - 1] = t.back();
    for(int i = n - 2;i >= 0;i--) {
        _mx[i] = max(t[i],_mx[i + 1]);
        _mn[i] = min(t[i],_mn[i + 1]);
    }
    t_[n] = build1();
    for(int i = n - 1;i >= 0;i--) {
        // cout << i << ' ' << t[i] << ' ' << val[t[i]] << '\n';   
        t_[i] = upd(t_[i + 1],t[i]);
    }
}
bool fq = true;
int up[N * 2][20],up1[N * 2][20];
int F(int x) {
    if(x < n) return x;
    return x - n;
}

bool solver(int x,int y,int d) {
    int l = x,r = y + 1;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(x,mid).first >= h[x] + d) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if(r == y + 1) {
        return false;
    }
    x = r;
    node _ = Get(x,y);
    return (_.ans >= d);
}
bool solvel(int x,int y,int d) {
    int l = x - 1,r = y;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(get1(mid,y).first >= h[y] + d) {
            l = mid;
        }else {
            r = mid;
        }
    }
    // cout << x << ' ' << y << ' ' << l << '\n';
    if(l == x - 1) return false;
    y = l;
    node _ = Get(x,y);
    return (_.ans1 >= d);
}
int max_towers(int l_, int r_, int d) {
    int it = lower_bound(b.begin(),b.end(),d) - b.begin();
    int ret = 0;
    int l,r;
    if(it == (int)b.size()) {
        l = r = get(l_,r_).second;
        ret++;
    } else {
        l = get_mn(l_,r_,t_[it]);
        r = get_mx(l_,r_,t_[it]);
        ret = get_sum(l_,r_,t_[it]);
    }
    return ret + solvel(l_,l,d) + solver(r,r_,d); 
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 116692 KB Output is correct
2 Correct 688 ms 161712 KB Output is correct
3 Correct 690 ms 161744 KB Output is correct
4 Correct 680 ms 161744 KB Output is correct
5 Correct 753 ms 161744 KB Output is correct
6 Correct 787 ms 161744 KB Output is correct
7 Correct 741 ms 161744 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 6 ms 44888 KB Output is correct
5 Correct 5 ms 44888 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44812 KB Output is correct
11 Runtime error 49 ms 106908 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 6 ms 44888 KB Output is correct
5 Correct 5 ms 44888 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44812 KB Output is correct
11 Runtime error 49 ms 106908 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 698 ms 335860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 77400 KB Output is correct
2 Correct 667 ms 161356 KB Output is correct
3 Correct 698 ms 161352 KB Output is correct
4 Correct 741 ms 161420 KB Output is correct
5 Correct 700 ms 161404 KB Output is correct
6 Correct 713 ms 161356 KB Output is correct
7 Correct 732 ms 161356 KB Output is correct
8 Correct 749 ms 161780 KB Output is correct
9 Correct 666 ms 161728 KB Output is correct
10 Correct 694 ms 161744 KB Output is correct
11 Correct 685 ms 161660 KB Output is correct
12 Correct 113 ms 161352 KB Output is correct
13 Correct 107 ms 161348 KB Output is correct
14 Correct 105 ms 161352 KB Output is correct
15 Correct 88 ms 161744 KB Output is correct
16 Correct 82 ms 161724 KB Output is correct
17 Correct 106 ms 158148 KB Output is correct
18 Correct 102 ms 161488 KB Output is correct
19 Correct 118 ms 161360 KB Output is correct
20 Correct 102 ms 161356 KB Output is correct
21 Correct 108 ms 161352 KB Output is correct
22 Correct 105 ms 161360 KB Output is correct
23 Correct 102 ms 161352 KB Output is correct
24 Correct 82 ms 161944 KB Output is correct
25 Correct 92 ms 161744 KB Output is correct
26 Correct 81 ms 161744 KB Output is correct
27 Correct 88 ms 161748 KB Output is correct
28 Correct 4 ms 44888 KB Output is correct
29 Correct 5 ms 44888 KB Output is correct
30 Correct 5 ms 44888 KB Output is correct
31 Correct 6 ms 44888 KB Output is correct
32 Correct 5 ms 44888 KB Output is correct
33 Correct 4 ms 40024 KB Output is correct
34 Correct 5 ms 44888 KB Output is correct
35 Correct 5 ms 44888 KB Output is correct
36 Correct 6 ms 44888 KB Output is correct
37 Correct 6 ms 44888 KB Output is correct
38 Correct 5 ms 44888 KB Output is correct
39 Correct 5 ms 44888 KB Output is correct
40 Correct 5 ms 44892 KB Output is correct
41 Correct 5 ms 44888 KB Output is correct
42 Correct 5 ms 44892 KB Output is correct
43 Correct 5 ms 44888 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 37464 KB Output is correct
2 Correct 5 ms 44888 KB Output is correct
3 Correct 5 ms 44888 KB Output is correct
4 Correct 6 ms 44888 KB Output is correct
5 Correct 5 ms 44888 KB Output is correct
6 Correct 5 ms 44888 KB Output is correct
7 Correct 5 ms 44888 KB Output is correct
8 Correct 5 ms 44888 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44812 KB Output is correct
11 Runtime error 49 ms 106908 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 116692 KB Output is correct
2 Correct 688 ms 161712 KB Output is correct
3 Correct 690 ms 161744 KB Output is correct
4 Correct 680 ms 161744 KB Output is correct
5 Correct 753 ms 161744 KB Output is correct
6 Correct 787 ms 161744 KB Output is correct
7 Correct 741 ms 161744 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 5 ms 44888 KB Output is correct
10 Correct 5 ms 44888 KB Output is correct
11 Correct 4 ms 37464 KB Output is correct
12 Correct 5 ms 44888 KB Output is correct
13 Correct 5 ms 44888 KB Output is correct
14 Correct 6 ms 44888 KB Output is correct
15 Correct 5 ms 44888 KB Output is correct
16 Correct 5 ms 44888 KB Output is correct
17 Correct 5 ms 44888 KB Output is correct
18 Correct 5 ms 44888 KB Output is correct
19 Correct 5 ms 44888 KB Output is correct
20 Correct 5 ms 44812 KB Output is correct
21 Runtime error 49 ms 106908 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -