oj.uz

Submission #646107

# Submission time Handle Problem Language Result Execution time Memory
646107 2022-09-28T17:07:21 Z NintsiChkhaidze Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 4672 KB 
#include "towers.h"
#include <bits/stdc++.h>
#define pb push_back
#define left (h<<1),l ,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 100005;
int n,a[N],l,r,d,L[N],R[N],t[4*N];
deque <int> dq;

void find(){
  while(dq.size()) dq.pop_front();
  
  for (int i =l; i <= r; i++){
    L[i] = l;
    while (dq.size() && a[dq.back()] < a[i] + d) dq.pop_back();
    if (dq.size()) L[i] = dq.back();
    while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
  }

  while(dq.size()) dq.pop_front();
  for (int i = r; i >= l; i--){
    R[i] = r;
    while (dq.size() && a[dq.back()] < a[i] + d) dq.pop_back();
    if (dq.size()) R[i] = dq.back();
    while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
    
    dq.push_back(i);
  }
}

void build(int h,int l,int r){
  if (l== r){
    t[h]=a[l];
    return;
  }
  build(left);
  build(right);
  t[h] = min(t[h*2],t[h*2+1]);
}

int getmin(int h,int l,int r,int L,int R){
  if (r < L || R < l) return 1e9;
  if (L <= l && r <= R) return t[h];
  return min(getmin(left,L,R),getmin(right,L,R));
}
void init(int N, vector<int> H) {
  n = N;
  for (int i = 1; i <= n; i++)
    a[i] = H[i-1];

  build(1,1,n);
}

int max_towers(int lf, int rg, int D) {
  l=lf+1,r=rg+1,d=D;
  find();
  vector <pair<int,int> > vec; vec.clear();
  for (int i = l; i <= r; i++)
    vec.pb({a[i],i});
  
  sort(vec.begin(),vec.end());
  int ans=0;
  for (auto [x,id]: vec){
    if (getmin(1,1,n, L[id], R[id]) < x) continue;
    ans++;
  }
  return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4099 ms 2860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '292', found: '283'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '292', found: '283'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 4672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4091 ms 1656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '292', found: '283'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4099 ms 2860 KB Time limit exceeded
2 Halted 0 ms 0 KB -