oj.uz

Submission #790934

# Submission time Handle Problem Language Result Execution time Memory
790934 2023-07-23T09:32:55 Z penguinman Radio Towers (IOI22_towers) C++17
0 / 100
 995 ms 4660 KB 
#include "towers.h"

#include <bits/stdc++.h>

using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(), a.end()
#define mp std::make_pair
#define pb emplace_back
constexpr ll inf = (1<<30)+(1<<29)+(1<<28);

ll N;
vi H;
vi right, left;
vi safe;

void init(int n, std::vector<int> h) {
  N = n;
  H.resize(N);
  right.resize(N);
  left.resize(N);
  rep(i,0,N) H[i] = h[i];
}

int max_towers(int L, int R, int D) {
  if(safe.empty()){
    rep(i,0,N) left[i] = 0, right[i] = inf;
    while(true){
        vi mid(N);
        vi flag(N);
        bool fff = true;
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                flag[i] = true;
                fff = false;
            }
        }
        if(fff) break;
    {
      std::deque<ll> ima, vma, imi, vmi;
      ima.pb(-3);
      vma.pb(-inf);
      imi.pb(-2);
      vmi.pb(inf);
      rep(i,0,N){
        ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small >= large) flag[i] = false;
        while(true){
          if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
          else break;
        }
        vma.pb(H[i]);
        ima.pb(i);
        while(true){
          if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
          else break;
        }
        vmi.emplace_front(H[i]);
        imi.emplace_front(i);
      }
    }
    {
      std::deque<ll> ima, vma, imi, vmi;
      ima.pb(N+3);
      vma.pb(-inf);
      imi.pb(N+2);
      vmi.pb(inf);
      per(i,N-1,0){
        ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small <= large) flag[i] = false;
        while(true){
          if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
          else break;
        }
        vma.pb(H[i]);
        ima.pb(i);
        while(true){
          if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
          else break;
        }
        vmi.emplace_front(H[i]);
        imi.emplace_front(i);
      }
    }
    rep(i,0,N){
        if(left[i]+1 < right[i]){
            if(flag[i]) left[i] = mid[i];
            else right[i] = mid[i];
        }
    }
    }
    safe = left;
    sort(all(safe));
  }
  ll ans = safe.end()-lower_bound(all(safe), D);
  return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 850 ms 3684 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 995 ms 4660 KB 1st lines differ - on the 1st token, expected: '11903', found: '33010'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 1360 KB 1st lines differ - on the 1st token, expected: '7197', found: '8637'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 208 KB 1st lines differ - on the 1st token, expected: '13', found: '131'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 850 ms 3684 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -