oj.uz

Submission #790803

# Submission time Handle Problem Language Result Execution time Memory
790803 2023-07-23T08:07:55 Z penguinman Radio Towers (IOI22_towers) C++17
0 / 100
 4000 ms 2224 KB 
#include "towers.h"

#include <bits/stdc++.h>

using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = int;
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);

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

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];
  D = -1;
}

int max_towers(int L, int R, int d) {
  if(D == -1){
    D = d;
    {
      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]+D)-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small >= large) left[i] = small+1;
        else left[i] = -1;
        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]+D)-vmi.begin();
        large = imi[large];
        ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
        small = ima[small];
        if(small <= large) right[i] = small-1;
        else right[i] = N;
        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);
      }
    }
  }
  ll ans = 0;
  REP(idx,L,R){
    if(left[idx] <= L && R <= right[idx]) ans++;
  }
  return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1155 ms 1584 KB 2nd lines differ - on the 1st token, expected: '1', found: '1622'
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 384 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
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 384 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3243 ms 740 KB 2nd lines differ - on the 1st token, expected: '7063', found: '7197'
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 384 KB 1st lines differ - on the 1st token, expected: '292', found: '293'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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