제출 #1131943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131943		byunjaewoo	송신탑 (IOI22_towers)	C++20	0 / 100	4038 ms	23188 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

const int N=100010, S=(1<<18);
int n, ans=1, a[N], d[N];
vector<int> c;
vector<int> v[N];

class seg {
public:
  void update(int k, int v) {
    k+=S-1;
    tree[k]=max(tree[k], v);
    for(k>>=1; k; k>>=1) tree[k]=max(tree[k], v);
  }
  int query(int l, int r) {
    int ret=0;
    for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
      if(l&1) ret=max(ret, tree[l++]);
      if(!(r&1)) ret=max(ret, tree[r--]);
    }
    if(l==r) ret=max(ret, tree[l]);
    return ret;
  }
private:
  int tree[2*S];
}T1, T2;

void init(int N, vector<int> H) {
  n=N;
  for(int i=1; i<=n; i++) a[i]=H[i-1];
}

int max_towers(int L, int R, int D) {
  L++, R++;
  fill(d+L, d+R+1, 1);
  for(int i=L; i<=R; i++) T1.update(i, a[i]);
  for(int i=L; i<=R; i++) {
    int tmp=R+1;
    for(int s=i+1, e=R; s<=e; ) {
      int m=(s+e)/2;
      if(T1.query(i+1, m)>=a[i]+D) tmp=m, e=m-1;
      else s=m+1;
    }
    v[tmp+1].push_back(i);
  }
  for(int i=L; i<=R; i++) c.push_back(a[i]), c.push_back(a[i]-D);
  sort(c.begin(), c.end()), c.erase(unique(c.begin(), c.end()), c.end());
  for(int i=L; i<=R; i++) {
    for(int j:v[i]) T2.update(lower_bound(c.begin(), c.end(), a[i-1]-D)-c.begin()+1, d[j]+1);
    int t=lower_bound(c.begin(), c.end(), a[i])-c.begin()+1;
    d[i]=max(d[i], T2.query(t, S));
    T2.update(t, T2.query(1, t));
    ans=max(ans, d[i]);
  }
  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