Submission #1032462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032462		Mr_Husanboy	Radio Towers (IOI22_towers)	C++17	14 / 100	685 ms	1880 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;
  }
};
vector<int> pref;

void init(int N, std::vector<int> H) {
  n = N;
  h = H;
  pref.resize(n);
  for(int i = 1; i < n - 1; i ++){
    if(h[i] > h[i - 1] && h[i] > h[i + 1]) pref[i] = 1;
  }
  for(int i = 1; i < n; i ++) pref[i] += pref[i - 1];
}

int max_towers(int l, int r, int d) {
  if(l == r) return 1;
  return pref[r - 1] - pref[l] + 1;
}

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