제출 #1032455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032455		Mr_Husanboy	송신탑 (IOI22_towers)	C++17	23 / 100	4050 ms	9296 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;


#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){
    return a.size();
}

int n;
vector<int> h;

int mx = 0;

struct SegTree{
  int n;
  vector<int> t;
  SegTree(int n) : n(n), t(2 * n){}
  SegTree(){}

  int merge(int a, int b){
    return max(a, b);
  }

  void upd(int i, int x){
    i += n;
    t[i] = max(t[i], x);
    for(i /= 2; i > 0; i /= 2){
      t[i] = merge(t[i * 2], t[i * 2 + 1]);
    }
  }

  int get(int l, int r){
    l += n; r += n;
    int res = 0;
    while(l <= r){
      if(l & 1){
        res = merge(res, t[l ++]);
      }
      if(!(r & 1)) res = merge(res, t[r --]); 
      l /= 2;
      r /= 2;
    }
    return res;
  }
};

void init(int N, std::vector<int> H) {
  n = N;
  h = H;
  for(int i = 0; i < n; i ++){
    if(h[mx] < h[i]){
      mx = i;
    }
  }
}

int max_towers(int l, int r, int d) {
  vector<int> hh;
  for(int i = l; i <= r; i ++) hh.push_back(h[i]), hh.push_back(h[i] - d),hh.push_back(h[i] + d);
  sort(all(hh));
  hh.erase(unique(all(hh)), hh.end());
  auto getid = [&](int x)->int{
    return lower_bound(all(hh), x) - hh.begin();
  };
  SegTree st1(len(hh) + 1), st2(len(hh) + 1);

  for(int i = l; i <= r; i ++){
    int j = getid(h[i]);
    st1.upd(j, st2.get(getid(h[i] + d), len(hh)) + 1);
    st2.upd(j, st1.get(0, getid(h[i] - d)));
    //cout << st2.get(j, j) << ' ';
  }
  return st1.get(0, len(hh));
}

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