Submission #764239

#	Time	Username	Problem	Language	Result	Execution time	Memory
764239		raysh07	Radio Towers (IOI22_towers)	C++17	23 / 100	4035 ms	18388 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 69;
int a[maxn];
int n;
map <int, int> mp, inv;
vector <int> b;
int dp[maxn][2];
int seg[4 * maxn][2];

void upd(int l, int r, int pos, int qp, int v, int i){
    if (l == r){
        seg[pos][i] = v;
        return;
    }
    int mid = (l + r)/2;
    if (qp <= mid) upd(l, mid, pos*2, qp, v, i);
    else upd(mid + 1, r, pos*2 + 1, qp, v, i);
    
    seg[pos][i] = max(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}

int query(int l, int r, int pos, int ql, int qr, int i){
    if (l >= ql && r <= qr) return seg[pos][i];
    else if (l > qr || r < ql) return 0;
    
    int mid = (l + r)/2;
    return max(query(l, mid, pos*2, ql, qr, i), query(mid + 1, r, pos*2 + 1, ql, qr, i));
}
 
void init(int N, vector<int> H) {
    n = N;
    for (int i = 0; i < N; i++){
        a[i + 1] = H[i];
    }
    
    set <int> st;
    for (int i = 1; i <= n; i++) st.insert(a[i]);
    int ptr = -1;
    st.insert(-1e9);
    st.insert(2e9 + 1);
    for (auto x : st){
        mp[x] = ++ptr;
        inv[ptr] = x;
        b.push_back(x);
    }
    
    for (int i = 1; i <= n; i++) {
        a[i] = mp[a[i]];
    }
}
 
int max_towers(int l, int r, int d) {
    l++;
    r++;
    int ans = 0;
    
    for (int i = l; i <= r; i++){
        int x = inv[a[i]];
        
        int pos = upper_bound(b.begin(), b.end(), x - d) - b.begin() - 1;
        dp[i][0] = query(1, n, 1, 1, pos, 0);
        upd(1, n, 1, a[i], dp[i][0], 1);
        
        pos = lower_bound(b.begin(), b.end(), x + d) - b.begin();
        dp[i][1] = 1 + query(1, n, 1, pos, n, 1);
        upd(1, n, 1, a[i], dp[i][1], 0);
        
        ans = max(ans, dp[i][0]);
        ans = max(ans, dp[i][1]);
    }
    
    return ans;
}

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