Submission #626871

#	Time	Username	Problem	Language	Result	Execution time	Memory
626871		Monchito	Radio Towers (IOI22_towers)	C++17	27 / 100	4030 ms	5028 KiB

towers

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

#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

const int INF = 1e9 + 7;
const int MAXN = 1e5;

struct Node{
  int val;
  Node(){val = -INF;}
  void init(int _val){val = _val;}
};
Node merge(Node l, Node r){
  Node ret; ret.init(max(l.val, r.val));
  return ret;
}

bool subtask1 = true;
int n, k=0;
vector<int> h;

Node st[MAXN * 2];
void build(){
  for(int i=n-1; i>0; i--) st[i] = merge(st[i<<1],st[i<<1|1]);
}
void update(int p, Node val){
  for(st[p+=n] = val; p>>=1;) st[p] = merge(st[p<<1],st[p<<1|1]); 
}
Node query(int l, int r){
  Node resl, resr;
  for(l+=n, r+=n; l<r; l>>=1, r>>=1){
    if(l&1) resl=merge(resl,st[l++]);
    if(r&1) resr=merge(st[--r],resr);
  }
  return merge(resl, resr);
}

void init(int N, vector<int> H) {
  n = N;
  h = H;

  for(int i=1; i<n; i++){
    if(h[i] < h[i-1]) break;
    k = i;
  }
  for(int i=0; i<k; i++) subtask1 &= h[i] < h[k];
  for(int i=k+1; i<n; i++) subtask1 &= h[i] < h[k];
  for(int i=1; i<k; i++) subtask1 &= h[i-1] < h[i];
  for(int i=k+1; i<n; i++) subtask1 &= h[i] < h[i-1];

  for(int i=0; i<n; i++) st[i+n].init(h[i]);
  build();
}

int max_towers(int L, int R, int D) {
  if(subtask1){
    if(R < k || L > k || R - L + 1 < 3 || L == k || R == k) return 1;
    return (h[L] <= h[k] - D && h[R] <= h[k] - D) ? 2 : 1; 
  } 
  if (R - L + 1 < 3) return 1;

  vector<pair<int,int>> q;
  for(int i = L; i <= R; i++) q.pb(mp(h[i], i));
  sort(all(q));
  
  set<int> used;
  used.insert(q[0].snd);

  for(int i = 1; i < sz(q); i++){
    bool can=true;
    auto it = used.lower_bound(q[i].snd);
    if(it == used.end()) it--;

    int l = *it, r=q[i].snd;
    if(l>r) swap(l,r);
    if(r-l+1<3) can=false;
    else{
        int hk = query(l+1, r).val;
        if(!(h[l] <= hk - D && h[r] <= hk - D))
          can=false;
    }
    if(it != used.begin()){
      it--;
      l = *it, r=q[i].snd;
      if(l>r) swap(l,r);
      if(r-l+1<3) can=false;
      else{
        int hk = query(l+1, r).val;
        if(!(h[l] <= hk - D && h[r] <= hk - D))
          can=false;
      }
    }
    if(can) used.insert(q[i].snd);
  }
  return sz(used);
}

• Subtask 1: 4 / 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