| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 629712 | peti1234 | Radio Towers (IOI22_towers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int c=100005, sok=2e9+5;
int n, t[c], maxi;
bool tc1=1, fontos[c];
set<pair<int, int> > tc5;
set<int> pos;
set<pair<int, int> > dif;
int kul(int a, int b) {
return abs(t[a]-t[b]);
}
void sub(int p) {
auto it=pos.find(p);
int el=0, kov=0;
it++;
kov=(*it);
it--, it--;
el=(*it);
pos.erase(p);
dif.erase({kul(p, kov), p});
dif.erase({kul(el, p), el});
dif.insert({kul(el, kov), el});
}
void calc_tc5() {
fontos[0]=1;
int ut=sok, ans=0, id=1;
for (int i=1; i<=n+1; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut>t[i]) {
fontos[i-1]=1;
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]>ut) {
fontos[i-1]=1;
ut=t[i];
id=1;
}
}
}
int el=-1;
for (int i=0; i<=n+1; i++) {
if (!fontos[i]) continue;
pos.insert(i);
if (el!=-1) {
dif.insert({kul(el, i), el});
//cout << "fontos " << el << " " << i << "\n";
}
el=i;
}
tc5.insert({0, ans});
while (ans>1) {
auto it=dif.begin();
int ert=(*it).first, p=(*it).second;
auto it2=pos.upper_bound(p);
int kov=*it2;
sub(p), sub(kov);
ans--;
//cout << ert << " " << ans << "\n";
it=tc5.upper_bound({ert, ans});
if (it!=tc5.end()) tc5.erase(it);
tc5.insert({ert, ans});
}
}
void init(int N, vector<int> sz) {
n=N;
for (int i=0; i<n; i++) {
t[i+1]=sz[i];
if (t[i+1]>t[maxi]) maxi=i+1;
}
t[0]=sok, t[n+1]=sok;
for (int i=1; i<=n; i++) {
if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
tc1=0;
}
}
calc_tc5();
}
int lassu(int l, int r, int d) {
int ut=t[l]+d, ans=0, id=1;
for (int i=l; i<=r; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut-t[i]>=d) {
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]-ut>=d) {
ut=t[i];
id=1;
}
}
}
return ans;
}
int max_towers(int l, int r, int d) {
l++, r++;
if (tc1) {
if (l<=maxi && maxi<=r && max(t[l], t[r])+d<=t[maxi]) return 2;
return 1;
}
if (l==1 && r==n) {
auto it=tc5.upper_bound({d, 0});
it--;
return (*it).second;
}
return lassu(l, r, d);
}
int main()
{
int N;
vector<int> P;
cin >> N;
for (int i=0; i<N; i++) {
int x;
cin >> x;
P.push_back(x);
}
init(N, P);
int q;
cin >> q;
while (q--) {
int l, r, d;
cin >> l >> r >> d;
cout << max_towers(l, r, d) << "\n";
}
return 0;
}
/*
7
6 7 4 5 2 3 1
*/
/*
7
1 2 6 4 5 3 7
*/