제출 #790934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790934		penguinman	송신탑 (IOI22_towers)	C++17	0 / 100	995 ms	4660 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(), a.end()
#define mp std::make_pair
#define pb emplace_back
constexpr ll inf = (1<<30)+(1<<29)+(1<<28);

ll N;
vi H;
vi right, left;
vi safe;

void init(int n, std::vector<int> h) {
  N = n;
  H.resize(N);
  right.resize(N);
  left.resize(N);
  rep(i,0,N) H[i] = h[i];
}

int max_towers(int L, int R, int D) {
  if(safe.empty()){
    rep(i,0,N) left[i] = 0, right[i] = inf;
    while(true){
        vi mid(N);
        vi flag(N);
        bool fff = true;
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                flag[i] = true;
                fff = false;
            }
        }
        if(fff) break;
    {
      std::deque<ll> ima, vma, imi, vmi;
      ima.pb(-3);
      vma.pb(-inf);
      imi.pb(-2);
      vmi.pb(inf);
      rep(i,0,N){
        ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small >= large) flag[i] = false;
        while(true){
          if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
          else break;
        }
        vma.pb(H[i]);
        ima.pb(i);
        while(true){
          if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
          else break;
        }
        vmi.emplace_front(H[i]);
        imi.emplace_front(i);
      }
    }
    {
      std::deque<ll> ima, vma, imi, vmi;
      ima.pb(N+3);
      vma.pb(-inf);
      imi.pb(N+2);
      vmi.pb(inf);
      per(i,N-1,0){
        ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small <= large) flag[i] = false;
        while(true){
          if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
          else break;
        }
        vma.pb(H[i]);
        ima.pb(i);
        while(true){
          if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
          else break;
        }
        vmi.emplace_front(H[i]);
        imi.emplace_front(i);
      }
    }
    rep(i,0,N){
        if(left[i]+1 < right[i]){
            if(flag[i]) left[i] = mid[i];
            else right[i] = mid[i];
        }
    }
    }
    safe = left;
    sort(all(safe));
  }
  ll ans = safe.end()-lower_bound(all(safe), D);
  return ans;
}

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