Submission #1082613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082613		Wansur	Radio Towers (IOI22_towers)	C++17	100 / 100	1534 ms	43600 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;

int root[maxn], t[maxn * 30];
int L[maxn * 30], R[maxn * 30];
int p[20][maxn], lg[maxn];
int dp[maxn], a[maxn];
pair<int, int> ord[maxn];
map<int, int> position;
int n, nv;

int build(int l, int r){
    int v = ++nv;
    if(l == r) return v;
    int mid = l + r >> 1;
    L[v] = build(l, mid);
    R[v] = build(mid+1, r);
    return v;
}

int upd(int v, int tl, int tr, int pos, int x){
    int u = ++nv;
    if(tl == tr){
        t[u] = x;
        return u;
    }
    L[u] = L[v], R[u] = R[v];
    int mid = tl + tr >> 1;
    if(pos <= mid){
        L[u] = upd(L[v], tl, mid, pos, x);
    }
    else{
        R[u] = upd(R[v], mid+1, tr, pos, x);
    }
    t[u] = t[L[u]] + t[R[u]];
    return u;
}

int get(int v, int tl, int tr, int l, int r){
    if(tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return t[v];
    int mid = tl + tr >> 1;
    return get(L[v], tl, mid, l, r) + get(R[v], mid+1, tr, l, r);
}

int get(int v, int tl, int tr, int k){
    if(tl == tr) return tl;
    int mid = tl + tr >> 1;
    if(t[L[v]] >= k) return get(L[v], tl, mid, k);
    return get(R[v], mid+1, tr, k - t[L[v]]);
}

struct asd{
    int mx, mn, x, y;
} d[maxn * 4];

asd merge(asd x, asd y){
    if(x.mx < 0) return y;
    if(y.mx < 0) return x;
    x.x = max({x.x, y.x, y.mx - x.mn});
    x.y = max({x.y, y.y, x.mx - y.mn});
    x.mx = max(x.mx, y.mx);
    x.mn = min(x.mn, y.mn);
    return x;
}

void build(int v, int tl, int tr){
    if(tl == tr){
        d[v].mx = d[v].mn = a[tl];
        d[v].x = d[v].y = 0;
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        d[v] = merge(d[v*2], d[v*2+1]);
    }
}

asd query(int v, int tl, int tr, int l, int r){
    if(tl > r || l > tr) return {-1, -1, -1, -1};
    if(tl >= l && tr <= r) return d[v];
    int mid = tl + tr >> 1;
    return merge(query(v*2, tl, mid, l, r), query(v*2+1, mid+1, tr, l, r));
}

int get(int l, int r){
    if(l > r) return 0;
    int k = lg[r - l + 1];
    return max(p[k][l], p[k][r - (1 << k) + 1]);
}

void init(int N, std::vector<int> H) {
    n = N;
    for(int i=1;i<=n;i++){
        dp[i] = int(2e9) + 1;
        a[i] = p[0][i] = H[i - 1];
        position[a[i]] = i;
        if(i > 1) lg[i] = lg[i / 2] + 1;
    }
    for(int k=1;k<20;k++){
        for(int i=1;i + (1 << k) - 1 <= n;i++){
            p[k][i] = max(p[k-1][i], p[k-1][i + (1 << (k - 1))]);
        }
    }
    stack<int> s;
    for(int i=1;i<=n;i++){
        while(s.size() && a[s.top()] > a[i]){
            s.pop();
        }
        if(s.size()){
            dp[i] = get(s.top() + 1, i - 1);
        }
        s.push(i);
    }
    while(s.size()) s.pop();
    for(int i=n;i;i--){
        while(s.size() && a[s.top()] > a[i]){
            s.pop();
        }
        if(s.size()){
            dp[i] = min(dp[i], get(i + 1, s.top() - 1));
        }
        s.push(i);
        ord[i] = {dp[i] - a[i], i};
    }
    sort(ord + 1, ord + n + 1, [](pair<int, int> x, pair<int, int> y){
        return x > y;
    });
    root[0] = build(1, n);
    build(1, 1, n);
    for(int i=1;i<=n;i++){
        root[i] = upd(root[i-1], 1, n, ord[i].s, 1);
    }
}

int max_towers(int l, int r, int d) {
    l++, r++;
    int i = l, j = r, pos = 0;
    for(int tl = 1, tr = n; tl <= tr;){
        int mid = tl + tr >> 1;
        if(ord[mid].f >= d){
            pos = mid;
            tl = mid + 1;
        }
        else tr = mid - 1;
    }
    int sx = get(root[pos], 1, n, 1, l - 1) + 1, sy = get(root[pos], 1, n, l, r), ans = sy;
    if(sy == 0){
        i = j = position[query(1, 1, n, l, r).mn];
        ans = 1;
    }
    else{
        i = get(root[pos], 1, n, sx), j = get(root[pos], 1, n, sx + sy - 1);
    }

    int L = 0, R = 0;
    for(int tl = l + 1, tr = i - 1; tl <= tr;){
        int mid = tl + tr >> 1;
        if(query(1, 1, n, mid, i-1).mx >= a[i] + d){
            L = mid;
            tl = mid + 1;
        }
        else tr = mid - 1;
    }
    for(int tl = j + 1, tr = r - 1; tl <= tr;){
        int mid = tl + tr >> 1;
        if(query(1, 1, n, j + 1, mid).mx >= a[j] + d){
            R = mid;
            tr = mid - 1;
        }
        else tl = mid + 1;
    }
    if(L != 0 && query(1, 1, n, l, L).x >= d) ans++;
    if(R != 0 && query(1, 1, n, R, r).y >= d) ans++;
    return ans;
}

Compilation message (stderr)

towers.cpp: In function 'int build(int, int)':
towers.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int mid = l + r >> 1;
      |               ~~^~~
towers.cpp: In function 'int upd(int, int, int, int, int)':
towers.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int get(int, int, int, int, int)':
towers.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int get(int, int, int, int)':
towers.cpp:55:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'void build(int, int, int)':
towers.cpp:80:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
towers.cpp: In function 'asd query(int, int, int, int, int)':
towers.cpp:90:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:148:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
towers.cpp:166:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
towers.cpp:174:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~

• 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