Submission #651458

#	Time	Username	Problem	Language	Result	Execution time	Memory
651458		NaimSS	Radio Towers (IOI22_towers)	C++17	100 / 100	2055 ms	74840 KiB

towers

#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 DEBUG=0;

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

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 = (posD-1);
  if(DEBUG)cout << "POSD "<<posD<<" "<<seg_ver << 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 || fi==-1 || la==-1){
    value v = difTree->qry(1,n,L,R);
    int tot=0;
    if(v.best>=D)tot++;
    if(v.best2>=D)tot++;
    return max(1,tot);
  }
  return query(seg[seg_ver],1,n,fi,la) + difTree->tot(fi,la,L,R,D);
}

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