Submission #1170350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170350		KG07	Radio Towers (IOI22_towers)	C++20	100 / 100	807 ms	64280 KiB

towers

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

struct node{
  int L, R, C;
  node *left, *right;
  void init(){
    if(L < R){
      left = new node({L, (L+R)/2, 0, NULL, NULL});
      right = new node({(L+R)/2+1, R, 0, NULL, NULL});
      left->init();
      right->init();
    }
  }
  void update(int K, node *M){
    C++;
    if(L == R)return;
    if(K > (L+R)/2){
      left = M->left;
      right = new node({(L+R)/2+1, R, M->right->C, NULL, NULL});
      right->update(K, M->right);
    }
    else{
      right = M->right;
      left = new node({L, (L+R)/2, M->left->C, NULL, NULL});
      left->update(K, M->left);
    }
  }
  int count(int x, int y){
    if(L > y || R < x)return 0;
    if(x <= L && y >= R)return C;
    return left->count(x, y) + right->count(x, y);
  }
  int left_index(int N){
    if(N > R)return 0;
    if(L == R)return C?R:0;
    if(!C)return 0;
    int t = left->left_index(N);
    return t?t:right->left_index(N);
  }
  int right_index(int N){
    if(N < L)return 0;
    if(L == R)return C?R:0;
    if(!C)return 0;
    int t = right->right_index(N);
    return t?t:left->right_index(N);
  }
};

struct segment_tree{
  int n, m;
  int H[100001], A[300000], B[300000], C[300000], D[300000];
  node *T[100001];
  queue<int> q;
  vector<pair<int, int>> E;
  void init(int N, vector<int> M){
    n = N;
    for(int i = 0; i < N; i++){
      H[i+1] = M[i];
      q.push(M[i]);
    }
    init_tree(1, 1, N);
    for(int i = 1; i <= N; i++){
      if((i > 1 && H[i-1] < H[i]) || (i < N && H[i] > H[i+1]))continue;
      int K = 1e9;
      if(i > 1 && min_value(1, 1, i-1, 1, N) <= H[i])K = min(K, max_value(1, get_right(1, i-1, H[i], 1, N)+1, i-1, 1, N)-H[i]);
      if(i < N && min_value(1, i+1, N, 1, N) <= H[i])K = min(K, max_value(1, i+1, get_left(1, i+1, H[i], 1, N)-1, 1, N)-H[i]);
      E.push_back(make_pair(-K, i));
    }
    sort(E.begin(), E.end());
    for(int i = 0; i < E.size(); i++)E[i].first = -E[i].first;
    T[0] = new node({1, N, 0, NULL, NULL});
    T[0]->init();
    for(int i = 1; i <= E.size(); i++){
      T[i] = new node({1, N, i-1, NULL, NULL});
      T[i]->update(E[i-1].second, T[i-1]);
    }
  }
  void init_tree(int N, int l, int r){
    if(l == r){
      A[N] = q.front();
      B[N] = q.front();
      q.pop();
      return;
    }
    init_tree(2*N, l, (l+r)/2);
    init_tree(2*N+1, (l+r)/2+1, r);
    A[N] = min(A[2*N], A[2*N+1]);
    B[N] = max(B[2*N], B[2*N+1]);
    C[N] = max(B[2*N+1]-A[2*N], max(C[2*N], C[2*N+1]));
    D[N] = max(B[2*N]-A[2*N+1], max(D[2*N], D[2*N+1]));
  }
  int min_value(int N, int x, int y, int l, int r){
    if(x > r || y < l)return 1000000001;
    if(x <= l && y >= r)return A[N];
    return min(min_value(2*N, x, y, l, (l+r)/2), min_value(2*N+1, x, y, (l+r)/2+1, r));
  }
  int max_value(int N, int x, int y, int l, int r){
    if(x > r || y < l)return 0;
    if(x <= l && y >= r)return B[N];
    return max(max_value(2*N, x, y, l, (l+r)/2), max_value(2*N+1, x, y, (l+r)/2+1, r));
  }
  int find_left(int N, int M, int K, int l, int r){
    if(M > r)return 0;
    if(l == r)return B[N]<K?0:r;
    if(B[N] < K)return 0;
    int t = find_left(2*N, M, K, l, (l+r)/2);
    return t?t:find_left(2*N+1, M, K, (l+r)/2+1, r);
  }
  int find_right(int N, int M, int K, int l, int r){
    if(M < l)return 0;
    if(l == r)return B[N]<K?0:r;
    if(B[N] < K)return 0;
    int t = find_right(2*N+1, M, K, (l+r)/2+1, r);
    return t?t:find_right(2*N, M, K, l, (l+r)/2);
  }
  int get_left(int N, int M, int K, int l, int r){
    if(M > r)return 0;
    if(l == r)return A[N]>K?0:r;
    if(A[N] > K)return 0;
    int t = get_left(2*N, M, K, l, (l+r)/2);
    return t?t:get_left(2*N+1, M, K, (l+r)/2+1, r);
  }
  int get_right(int N, int M, int K, int l, int r){
    if(M < l)return 0;
    if(l == r)return A[N]>K?0:r;
    if(A[N] > K)return 0;
    int t = get_right(2*N+1, M, K, (l+r)/2+1, r);
    return t?t:get_right(2*N, M, K, l, (l+r)/2);
  }
  int left_difference(int N, int x, int y, int *X, int *Y, int l, int r){
    if(x > r || y < l)return 0;
    if(x <= l && y >= r){
      *X = min(*X, A[N]);
      *Y = max(*Y, B[N]);
      return C[N];
    }
    int a = 1e9, b = 0;
    int L = left_difference(2*N, x, y, &a, Y, l, (l+r)/2);
    int R = left_difference(2*N+1, x, y, X, &b, (l+r)/2+1, r);
    *X = min(*X, a);
    *Y = max(*Y, b);
    return max(b-a, max(L, R));
  }
  int right_difference(int N, int x, int y, int *X, int *Y, int l, int r){
    if(x > r || y < l)return 0;
    if(x <= l && y >= r){
      *X = max(*X, B[N]);
      *Y = min(*Y, A[N]);
      return D[N];
    }
    int a = 0, b = 1e9;
    int L = right_difference(2*N, x, y, &a, Y, l, (l+r)/2);
    int R = right_difference(2*N+1, x, y, X, &b, (l+r)/2+1, r);
    *X = max(*X, a);
    *Y = min(*Y, b);
    return max(a-b, max(L, R));
  }
  int left_value(int N, int M, int K, int *Z, int l, int r){
    if(M > r)return 0;
    if(l == r){
      if(B[N]-*Z>=K)return r;
      *Z = min(*Z, A[N]);
      return 0;
    }
    if(B[N]-*Z<K)return 0;
    int L = left_value(2*N, M, K, Z, l, (l+r)/2);
    if(L)return L;
    int R = left_value(2*N+1, M, K, Z, (l+r)/2+1, r);
    *Z = min(*Z, A[N]);
    return R;
  }
  int right_value(int N, int M, int K, int *Z, int l, int r){
    if(M < l)return 0;
    if(l == r){
      if(B[N]-*Z>=K)return r;
      *Z = min(*Z, A[N]);
      return 0;
    }
    if(B[N]-*Z<K)return 0;
    int a = 0, b = 1e9;
    int R = right_value(2*N+1, M, K, Z, (l+r)/2+1, r);
    if(R)return R;
    int L = right_value(2*N, M, K, Z, l, (l+r)/2);
    *Z = min(*Z, A[N]);
    return L;
  }
  int state(int N){
    int L = 0, R = E.size()-1;
    while(L < R){
      int c = (L+R+1)/2;
      if(E[c].first < N)R = (L+R)/2;
      else L = c;
    }
    return R+1;
  }
} T;

void init(int N, vector<int> H) {
  T.init(N, H);
}

int max_towers(int L, int R, int D) {
  node* E = T.T[T.state(D)];
  int t = E->count(L+1, R+1);
  if(!t){
    if(T.left_difference(1, L+1, R+1, new int(1e9), new int(0), 1, T.n) < D || T.right_difference(1, L+1, R+1, new int(0), new int(1e9), 1, T.n) < D)return 1;
    if(T.left_value(1, L+1, D, new int(1000000001), 1, T.n) > T.right_value(1, R+1,D, new int(1000000001), 1, T.n))return 1;
    return 2;
  }
  int X = E->left_index(L+1);
  int Y = E->right_index(R+1);
  if(X > L+1 && T.max_value(1, L+1, X-1, 1, T.n) >= T.H[X]+D && T.left_difference(1, L+1, T.find_right(1, X, T.H[X]+D, 1, T.n), new int(1e9), new int(0), 1, T.n) >= D)t++;
  if(Y < R+1 && T.max_value(1, Y+1, R+1, 1, T.n) >= T.H[Y]+D && T.right_difference(1, T.find_left(1, Y, T.H[Y]+D, 1, T.n), R+1, new int(0), new int(1e9), 1, T.n) >= D)t++;
  return t;
}

• 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