Submission #828420

#	Time	Username	Problem	Language	Result	Execution time	Memory
828420		OrazB	Radio Towers (IOI22_towers)	C++17	11 / 100	4033 ms	3992 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 5e5+5;
int n, m;
int red[4*N], mxt[4*N];
vector<int> h = {0};

int mxbin(int x, vector<int> vec){
int l = 0, r = m-1, pos = m;
while(l <= r){
int md = (l+r)>>1;
if (vec[md] < x) l = md + 1;
else{
pos = md;
r = md - 1;
}
}
return pos+1;
}

int mnbin(int x, vector<int> vec){
int l = 0, r = m-1, pos = -1;
while(l <= r){
int md = (l+r)>>1;
if (vec[md] <= x){
pos = md;
l = md + 1;
}else r = md - 1;
}
return pos+1;
}

int tap(int pos, int l = 1, int r = m, int idx = 1){
if (l > pos) return 0;
if (r <= pos) return red[idx];
int md = (l+r)>>1;
return max(tap(pos, l, md, idx<<1), tap(pos, md+1, r, idx<<1|1));
}

void upd(int pos, int x, int l = 1, int r = m, int idx = 1){
if (l == r){
red[idx] = max(red[idx], x);
return;
}
int md = (l+r)>>1;
if (pos <= md) upd(pos, x, l, md, idx<<1);
else upd(pos, x, md+1, r, idx<<1|1);
red[idx] = max(red[idx<<1], red[idx<<1|1]);
}

int mxtap(int pos, int l = 1, int r = m, int idx = 1){
if (r < pos) return 0;
if (l >= pos) return mxt[idx];
int md = (l+r)>>1;
return max(mxtap(pos, l, md, idx<<1), mxtap(pos, md+1, r, idx<<1|1));
}

void updmx(int pos, int x, int l = 1, int r = m, int idx = 1){
if (l == r){
mxt[idx] = max(mxt[idx], x);
return;
}
int md = (l+r)>>1;
if (pos <= md) updmx(pos, x, l, md, idx<<1);
else updmx(pos, x, md+1, r, idx<<1|1);
mxt[idx] = max(mxt[idx<<1], mxt[idx<<1|1]);
}

void init(int _n, vector<int> _h){
n = _n;
for (auto i : _h) h.pb(i);
}

int max_towers(int l, int r, int D){
int ans = 0;
vector<int> vec;
l++; r++;
for (int i = l; i <= r; i++) vec.pb(h[i]);
sort(all(vec));
m = vec.size();
for (int i = r; i >= l; i--){
int posj = mxbin(h[i]+D, vec);
int pos = mnbin(h[i]-D, vec);
int y = mxtap(posj)+1;
int x = tap(pos);
upd(mxbin(h[i], vec), y);
updmx(mxbin(h[i], vec), x);
ans = max(ans, y);

}
return ans;
}

// int main ()
// {
// ios::sync_with_stdio(false);
// cin.tie(0);
// int n, q;
// cin >> n >> q;
// vector<int> h(n);
// for (int i = 0; i < n; i++) cin >> h[i];
// init(n, h);
// while(q--){
// int l, r, d;
// cin >> l >> r >> d;
// cout << max_towers(l, r, d) << '\n';
// }
// } 

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