Submission #716571

#	Time	Username	Problem	Language	Result	Execution time	Memory
716571		Jarif_Rahman	Radio Towers (IOI22_towers)	C++17	100 / 100	1952 ms	216212 KiB

towers

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct segtree{
    int k = 1;
    vector<int> v;
    segtree(int n){
        while(k < n) k*=2;
        v.assign(2*k, 0);
    }
    void update(int i, int x){
        i+=k;
        v[i] = x;
        i/=2;
        while(i){
            v[i] = max(v[2*i], v[2*i+1]);
            i/=2;
        }
    }
    int get(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r) return v[nd];
        int md = (a+b)/2;
        return max(get(l, r, 2*nd, a, md), get(l, r, 2*nd+1, md+1, b));
    }
    int get(int l, int r){
        if(l > r) return 0;
        return get(l, r, 1, 0, k-1);
    }
};

struct persistent_segtree{
    struct Node{
        int x;
        Node *l = nullptr, *r = nullptr;
        Node(int _x = 0): x(_x){}
        Node(Node* _l, Node* _r): x(_l->x+_r->x), l(_l), r(_r){}
    };

    int k = 1;
    persistent_segtree(int n){
        while(k < n) k<<=1;
    }

    void init_rec(Node* nd, int a, int b){
        if(a == b) return;
        nd->l = new Node();
        nd->r = new Node();
        int md = (a+b)>>1;
        init_rec(nd->l, a, md);
        init_rec(nd->r, md+1, b);
    }
    Node* init(){
        auto nd = new Node();
        init_rec(nd, 0, k-1);
        return nd;
    }

    Node* update(Node* nd, int a, int b, int i, int x){
        if(a == b) return new Node(nd->x+x);
        int md = (a+b)>>1;
        if(i <= md) return new Node(update(nd->l, a, md, i, x), nd->r);
        return new Node(nd->l, update(nd->r, md+1, b, i, x));
    }
    Node* update(Node* nd, int i, int x){
        return update(nd, 0, k-1, i, x);
    }

    int sum(Node* nd, int a, int b, int l, int r){
        if(a > r || b < l) return 0;
        if(a >= l && b <= r) return nd->x;
        int md = (a+b)>>1;
        return sum(nd->l, a, md, l, r)+sum(nd->r, md+1, b, l, r);
    }
    int sum(Node* nd, int l, int r){
        if(l > r) return 0;
        return sum(nd, 0, k-1, l, r);
    }

    int first_one(Node* nd, int l, int r, int a, int b){
        if(a > r || b < l) return -1;
        if(nd->x == 0) return -1;
        if(a == b) return a;
        int md = (a+b)>>1;
        int rt = first_one(nd->l, l, r, a, md);
        if(rt == -1) return first_one(nd->r, l, r, md+1, b);
        return rt;
    }
    int first_one(Node *nd, int l, int r){
        return first_one(nd, l, r, 0, k-1);
    }
    int last_one(Node* nd, int l, int r, int a, int b){
        if(a > r || b < l) return -1;
        if(nd->x == 0) return -1;
        if(a == b) return a;
        int md = (a+b)>>1;
        int rt = last_one(nd->r, l, r, md+1, b);
        if(rt == -1) return last_one(nd->l, l, r, a, md);
        return rt;
    }
    int last_one(Node *nd, int l, int r){
        return last_one(nd, l, r, 0, k-1);
    }
};

int n;
vector<int> h;
segtree seg(0);
vector<int> DL, DR, DLR;
vector<int> SL, SR;

vector<int> cmpr;
map<int, int> mp;

persistent_segtree psL(0), psR(0), psLR(0);
vector<persistent_segtree::Node*> ndL, ndR, ndLR;

void init(int _n, vector<int> _h){
    swap(n, _n);
    swap(h, _h);
    seg = segtree(n);
    DR.assign(n, 1e9);
    DL.assign(n, 1e9);
    DLR.assign(n, 1e9);
    SL.assign(n, 0);
    SR.resize(n, n-1);

    for(int i = 0; i < n; i++) seg.update(i, h[i]);

    stack<int> st;
    for(int i = n-1; i >= 0; i--){
        while(!st.empty() && h[i] < h[st.top()]){
            SL[st.top()] = i;
            DL[st.top()] = max(0, seg.get(i, st.top())-h[st.top()]);
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = 0; i < n; i++){
        while(!st.empty() && h[i] < h[st.top()]){
            SR[st.top()] = i;
            DR[st.top()] = max(0, seg.get(st.top(), i)-h[st.top()]);
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()) st.pop();

    for(int i = 0; i < n; i++) cmpr.pb(DL[i]), cmpr.pb(DR[i]);
    sort(cmpr.begin(), cmpr.end());
    for(int i = 0; i < cmpr.size(); i++) mp[cmpr[i]] = i;
    for(int &x: DL) x = mp[x];
    for(int &x: DR) x = mp[x];
    for(int i = 0;  i < n; i++) DLR[i] = min(DL[i], DR[i]);

    psL = persistent_segtree(n);
    psR = persistent_segtree(n);
    psLR = persistent_segtree(n);
    ndL.resize(2*n);
    ndR.resize(2*n);
    ndLR.resize(2*n);

    vector<vector<int>> sth(2*n);

    ndL[2*n-1] = psL.init();
    for(int i = 0; i < n; i++) sth[DL[i]].pb(i);
    for(int i = 2*n-1; i >= 0; i--){
        if(i+1 < 2*n) ndL[i] = ndL[i+1];
        for(int j: sth[i]) ndL[i] = psL.update(ndL[i], j, 1);
        sth[i].clear();
    }

    ndR[2*n-1] = psR.init();
    for(int i = 0; i < n; i++) sth[DR[i]].pb(i);
    for(int i = 2*n-1; i >= 0; i--){
        if(i+1 < 2*n) ndR[i] = ndR[i+1];
        for(int j: sth[i]) ndR[i] = psR.update(ndR[i], j, 1);
        sth[i].clear();
    }

    ndLR[2*n-1] = psLR.init();
    for(int i = 0; i < n; i++) sth[DLR[i]].pb(i);
    for(int i = 2*n-1; i >= 0; i--){
        if(i+1 < 2*n) ndLR[i] = ndLR[i+1];
        for(int j: sth[i]) ndLR[i] = psLR.update(ndLR[i], j, 1);
        sth[i].clear();
    }
}

int max_towers(int L, int R, int D){
    auto it = lower_bound(cmpr.begin(), cmpr.end(), D);
    if(it == cmpr.end()) return 1;
    int d = mp[*it];

    int ans = psLR.sum(ndLR[d], L, R);
    if(ans == 0){
        int a = psR.first_one(ndR[d], L, R), b = psL.last_one(ndL[d], L, R);
        if(a != -1 && b != -1 && a < b) return 2;
        return 1;
    }

    int a = psLR.first_one(ndLR[d], L, R), b = psLR.last_one(ndLR[d], L, R);
    if(psR.sum(ndR[d], L, a-1) > 0) ans++;
    if(psL.sum(ndL[d], b+1, R) > 0) ans++;

    return ans;
}

Compilation message (stderr)

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i = 0; i < cmpr.size(); i++) mp[cmpr[i]] = i;
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 17 / 17
• Subtask 6: 19 / 19
• Subtask 7: 23 / 23