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 "towers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
ll T[LIM], jaki[LIM], n;
set<pair<ll,ll>>S, P;
vector<pair<ll,ll>>ans;
void dodaj(int x) {
auto it=S.lower_bound({x, -1}); ++it;
auto a=*it;
P.insert({abs(T[x]-T[a.st]), x});
}
void usun(int x) {
auto it=S.lower_bound({x, -1}); ++it;
auto a=*it;
P.erase({abs(T[x]-T[a.st]), x});
}
void init(int _n, vector<int>_H) {
n=_n;
rep(i, n) T[i+1]=_H[i];
T[0]=T[n+1]=INF;
int akt=2;
jaki[0]=jaki[n+1]=1;
rep(i, n) if((T[i]<T[i+1] && T[i+1]>T[i+2]) || (T[i]>T[i+1] && T[i+1]<T[i+2])) {
jaki[i+1]=akt;
akt^=3;
}
rep(i, n+2) if(jaki[i]) S.insert({i, jaki[i]});
auto it=S.begin();
while(true) {
auto it2=it; ++it2;
if(it2==S.end()) break;
auto a=*it;
dodaj(a.st);
++it;
}
ans.pb({0, S.size()/2});
while(P.size()>2) {
auto a=*P.begin();
usun(a.nd);
auto it=S.lower_bound({a.nd, -1});
++it;
auto b=*it;
usun(b.st);
--it; --it;
b=*it;
usun(b.st);
++it;
S.erase(it);
it=S.lower_bound({a.nd, -1});
S.erase(it);
it=S.lower_bound({a.nd, -1});
--it;
b=*it;
dodaj(b.st);
ans.pb({a.st, S.size()/2});
}
}
int max_towers(int l, int r, int d) {
int po=0, ko=ans.size()-1;
while(po<ko) {
int sr=(po+ko+1)/2;
if(ans[sr].st<d) po=sr; else ko=sr-1;
}
return ans[po].nd;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |