oj.uz

Submission #790882

# Submission time Handle Problem Language Result Execution time Memory
790882 2023-07-23T09:12:31 Z penguinman Radio Towers (IOI22_towers) C++17
0 / 100
 697 ms 66976 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)+(1<<29)+(1<<28);

ll N;
vi H;
ll D;
vi right, left;
constexpr ll di = 30;
ll sz;
vii pr, mr, pl, ml;
vii sum;

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;
    {
      sz = N/di+100;
      sum.resize(sz, vi(sz));
      pr.resize(N+2);
      mr.resize(N+2);
      pl.resize(N+2);
      ml.resize(N+2);
      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);
      }
    }
    rep(i,0,N){
      left[i]++;
      right[i]++;
      ll ld = (left[i]+di-1)/di;
      ll rd = right[i]/di;
      sum[ld][rd]++;
      ll id = i/di;
      sum[ld][id]--;
      id = (i+2+di-1)/di;
      sum[id][rd]--;
      pr[right[i]].pb(left[i]);
      pl[left[i]].pb(right[i]);
      ml[i+2].pb(right[i]);
      ml[left[i]].pb(i);
      mr[i].pb(left[i]);
      mr[right[i]].pb(i+2);
    }
    per(l,sz,0){
      rep(i,0,sz){
        ll j = i+l;
        if(j >= sz) break;
        if(i) sum[i][j] += sum[i-1][j];
        if(j+1 < sz) sum[i][j] += sum[i][j+1];
        if(i && j+1<sz) sum[i][j] -= sum[i-1][j+1];
      }
    }
    rep(i,0,pr.size()){
        sort(all(pr[i]));
        sort(all(pl[i]));
        sort(all(mr[i]));
        sort(all(ml[i]));
    }
  }
  ll ans = 0;
  L++, R++;
  ll ld = L/di;
  ll rd = (R+di-1)/di;
  ans = sum[ld][rd];
  REP(i, ld*di+1, L){
    ans += pl[i].end()-lower_bound(all(pl[i]), R);
    ans -= ml[i].end()-lower_bound(all(ml[i]), R);
  }
  rep(i,R,rd*di){
    if(i >= int(pr.size())) continue;
    ans += upper_bound(all(pr[i]), L)-pr[i].begin();
    ans -= upper_bound(all(mr[i]), L)-mr[i].begin();
  }
  return ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 423 ms 29996 KB 31st 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 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 1 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Incorrect 1 ms 720 KB 1st lines differ - on the 1st token, expected: '738', found: '734'
17 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 1 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Incorrect 1 ms 720 KB 1st lines differ - on the 1st token, expected: '738', found: '734'
17 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 66976 KB 1560th lines differ - on the 1st token, expected: '14836', found: '14827'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 262 ms 8532 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 1 ms 336 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 1 ms 720 KB Output is correct
14 Correct 1 ms 720 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Incorrect 1 ms 720 KB 1st lines differ - on the 1st token, expected: '738', found: '734'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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