#include "towers.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
#define ff first
#define ss second
const int N = 100100;
const int inf = 2e9;
int h[N];
// arvore para achar os indices l' e r':
struct value{
int mn,mx,best,best2;
value(){
mn = inf,mx=-inf,best=best2=-inf;
}
value operator+(const value &o)const{
value res;
res.mn = min(mn,o.mn);
res.mx = max(mx,o.mx);
res.best = max({best,o.best,o.mx - mn});
res.best2 = max({best2,o.best2,mx - o.mn});
return res;
}
};
int n;
struct node{
value v;
node *l,*r;
node(){
l=r=NULL;
}
void build(int i,int j,int h[]){
if(i == j){
v.mn = v.mx = h[i];
v.best = v.best2 = 0;
l = r = NULL;
return;
}
l = new node();
r = new node();
int m = (i+j)/2;
l->build(i,m,h);
r->build(m+1,j,h);
v = l->v + r->v;
}
// achar maior dif no segmento
value qry(int i,int j,int a,int b){
if(a == i && j == b)return v;
int m = (i+j)/2;
if(b<=m)return l->qry(i,m,a,b);
if(a > m)return r->qry(m+1,j,a,b);
return l->qry(i,m,a,m) + r->qry(m+1,j,m+1,b);
}
// achar maior L tal que H[L] >= X, e L <= R
int last(int i,int j,int X,int R){ // lembrar de passar (1,n,A[i]+D,i-1)
if(i>R)return -1;
if(v.mx < X)return -1;
if(i==j)return i;
int m = (i+j)/2;
int op1 = r->last(m+1,j,X,R);
if(op1!=-1)return op1;
return l->last(i,m,X,R);
}
int first(int i,int j,int X,int L){
if(j<L)return -1;
if(v.mx < X)return -1;
if(i==j)return i;
int m = (i+j)/2;
int op1 = l->first(i,m,X,L);
if(op1!=-1)return op1;
return r->first(m+1,j,X,L);
}
int good2(int n,int j,int R,int D){
int pos = first(1,n,h[j] + D,j+1);
if(pos == -1 || pos > R)return 0;
value v = qry(1,n,pos,R);
if(v.best2 >= D)return 1;
return 0;
}
int good(int n,int i,int L,int D){
int pos = last(1,n,h[i] + D,i-1);
if(pos==-1 || pos < L)return 0;
value v = qry(1,n,L,pos);
if(v.best >= D)return 1;
return 0;
}
int tot(int i,int j,int L,int R,int D){
return good(n,i,L,D) + good2(n,j,R,D);
}
};
node *difTree;
struct Node{
Node *l,*r;
int s=0;
Node(){
s=0,l=r=NULL;
}
};
void build(Node* no,int i,int j){
if(i == j){
return;
}
int m = (i+j)/2;
no->l = new Node();
no->r = new Node();
build(no->l,i,m),build(no->r,m+1,j);
}
void upd(Node *old,Node *nv,int i,int j,int p){
if(i == j){
nv->s = old->s ^ 1;
return;
}
int m = (i+j)/2;
if(p<=m){
nv->r = old->r;
nv->l = new Node();
upd(old->l,nv->l,i,m,p);
}else{
nv->l = old->l;
nv->r = new Node();
upd(old->r,nv->r,m+1,j,p);
}
nv->s = nv->l->s + nv->r->s;
}
int first(Node *no,int i,int j,int L,int R){
if(no->s == 0 || i > R || j < L)return -1;
if(i == j)return i;
int m = (i+j)/2;
int op1 = first(no->l,i,m,L,R);
if(op1!=-1)return op1;
return first(no->r,m+1,j,L,R);
}
int last(Node *no,int i,int j,int L,int R){
if(no->s == 0 || i > R || j < L)return -1;
if(i == j)return i;
int m = (i+j)/2;
int op1 = last(no->r,m+1,j,L,R);
if(op1!=-1)return op1;
return last(no->l,i,m,L,R);
}
int query(Node *no,int i,int j,int a,int b){
if(i > j || i>b || j < a)return 0;
if(a<=i && j<=b)return no->s;
int m = (i+j)/2;
return query(no->l,i,m,a,b) + query(no->r,m+1,j,a,b);
}
Node *seg[N];
set<piii> diffs; // {id, {mx_antes - mn, mx_dps - mn}}
set<pii> small; // {dif, id}
// id<0 quer dizer que é dif de id com id-1. se n com id+1
vector<int> delta; // D validos
const int DEBUG=0;
void init(int N, std::vector<int> H) {
n=N;
h[0] = inf;
rep(i,1,n+1)h[i] = H[i-1];
h[n+1] = inf;
difTree = new node();
difTree->build(1,n,h);
seg[0] = new Node();
build(seg[0],1,n);
piii curDif = {0,{inf,0}};
for(int i=1;i<=n+1;i++){
if(h[i] < min(h[i-1],h[i+1])){
// v
curDif.ff = i;
curDif.ss.ff-=h[i];
curDif.ss.ss=-h[i];
}
if(h[i] > max(h[i-1],h[i+1])){
// ^
curDif.ss.ss+=h[i];
diffs.insert(curDif);
curDif.ss.ff=h[i];
}
}
int seg_id = 0;
delta.pb(0);
for(auto it : diffs){
Node *no = new Node();
upd(seg[0],no,1,n,it.ff);
small.insert({it.ss.ff,-it.ff}); // dif de it.ff com it.ff-1
small.insert({it.ss.ss,it.ff}); // dif de it.ff com it.ff+1
seg[0] = no;
if(DEBUG)cout <<"upd "<<it.ff<<endl;
}
while(diffs.size() > 1){
pii mn = *small.begin();
auto it = diffs.lower_bound({abs(mn.ss),{-inf,-inf}}); // achar id mn.ss
piii curDif = *it;
if(DEBUG)cout << "upd "<<mn.ff<<" "<<abs(mn.ss) << endl;
if(delta.back()!=mn.first){
delta.pb(mn.first);
Node *no = new Node();
upd(seg[seg_id],no,1,n,abs(mn.ss));
seg[++seg_id] = no;
}else{
Node *no = new Node();
upd(seg[seg_id],no,1,n,abs(mn.ss));
seg[seg_id] = no;
}
if(mn.ss < 0){
// id com id-1:
piii ant = *--it;
diffs.erase(ant);
small.erase({ant.ss.ss,ant.ff});
ant.ss.ss += abs(curDif.ss.ss - curDif.ss.ff);// vale aumenta um pouco
small.insert({ant.ss.ss,ant.ff});
diffs.insert(ant);
}else{
piii nxt = *++it;
diffs.erase(nxt);
small.erase({nxt.ss.ff,-nxt.ff});
nxt.ss.ff += abs(curDif.ss.ss - curDif.ss.ff);// vale aumenta um pouco
small.insert({nxt.ss.ff,-nxt.ff});
diffs.insert(nxt);
}
diffs.erase(curDif);
small.erase({curDif.ss.ff,-curDif.ff});
small.erase({curDif.ss.ss,curDif.ff});
}
if(DEBUG)cout<<"DELTA\n";
for(auto it : delta)if(DEBUG)cout<<it<<" ";
if(DEBUG)cout << endl;
}
int max_towers(int L, int R, int D) {
L++,R++;
if(DEBUG)cout << "QUERY "<<L<<" "<<R<<" "<<D<<endl;
int posD = lower_bound(delta.begin(),delta.end(),D) - delta.begin();
if(posD == (int)delta.size())return 1;
int seg_ver = (delta[posD] == D ? posD-1 : posD);
if(DEBUG)cout << "POSD "<<posD<<endl;
int fi = first(seg[seg_ver],1,n,L,R);
int la = last(seg[seg_ver],1,n,L,R);
if(DEBUG)cout << "fi and la: "<<fi<<" "<<la<<endl;
if(fi > la)return 1;
return query(seg[seg_ver],1,n,fi,la) + difTree->tot(fi,la,L,R,D);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
491 ms |
10284 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1104 KB |
1st lines differ - on the 1st token, expected: '91', found: '90' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1104 KB |
1st lines differ - on the 1st token, expected: '91', found: '90' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1057 ms |
54984 KB |
1st lines differ - on the 1st token, expected: '11903', found: '11902' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
12480 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7196' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1104 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1104 KB |
1st lines differ - on the 1st token, expected: '91', found: '90' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
491 ms |
10284 KB |
1st lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
