oj.uz

Submission #1077593

# Submission time Handle Problem Language Result Execution time Memory
1077593 2024-08-27T08:10:46 Z Hanksburger Radio Towers (IOI22_towers) C++17
17 / 100
 877 ms 30920 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int seg[400005], order[100005], a[100005], n;
vector<int> h, seglist[400005];
set<int> s;
bool cmp(int x, int y)
{
  return h[x]<h[y];
}
void build(int i, int l, int r)
{
  if (l==r)
  {
    if (l==-1 || l==n)
      seg[i]=2e9;
    else
      seg[i]=h[l];
    return;
  }
  int m=(l+r+2)/2-1;
  build(i*2, l, m);
  build(i*2+1, m+1, r);
  seg[i]=max(seg[i*2], seg[i*2+1]);
}
int query(int i, int l, int r, int ql, int qr)
{
  if (ql<=l && r<=qr)
    return seg[i];
  int m=(l+r+2)/2-1, res=0;
  if (ql<=m && l<=qr)
    res=max(res, query(i*2, l, m, ql, qr));
  if (ql<=r && m<qr)
    res=max(res, query(i*2+1, m+1, r, ql, qr));
  return res;
}
void buildlist(int i, int l, int r)
{
  if (l==r)
  {
    seglist[i].push_back(a[l]);
    //cout << i << ' ' << a[l] << '\n';
    return;
  }
  int m=(l+r)/2;
  buildlist(i*2, l, m);
  buildlist(i*2+1, m+1, r);
  for (int x:seglist[i*2])
    seglist[i].push_back(x);
  for (int x:seglist[i*2+1])
    seglist[i].push_back(x);
  sort(seglist[i].begin(), seglist[i].end());
}
int querylist(int i, int l, int r, int ql, int qr, int x)
{
  if (ql<=l && r<=qr)
  {
    int ind=lower_bound(seglist[i].begin(), seglist[i].end(), x)-seglist[i].begin();
    //cout << l << ' ' << r << ": ";
    //for (int x:seglist[i])
    //    cout << x << ' ';
    //cout << "    " << ind << '\n';
    return seglist[i].size()-ind;
  }
  int m=(l+r)/2, res=0;
  if (ql<=m && l<=qr)
    res+=querylist(i*2, l, m, ql, qr, x);
  if (ql<=r && m<qr)
    res+=querylist(i*2+1, m+1, r, ql, qr, x);
  return res;
}
void init(int N, vector<int> H)
{
  n=N;
  h=H;
  build(1, -1, n);
  for (int i=0; i<n; i++)
    order[i]=i;
  sort(order, order+n, cmp);
  s.insert(-2);
  s.insert(n+1);
  for (int i=0; i<n; i++)
  {
    int ind=order[i];
    auto it=s.lower_bound(ind);
    int l=*prev(it), r=*it;
    int res1=(ind-l==1?0:query(1, -1, n, l+1, ind-1));
    int res2=(r-ind==1?0:query(1, -1, n, ind+1, r-1));
    a[ind]=min(res1, res2)-h[ind];
    s.insert(ind);
  }
  buildlist(1, 0, n-1);
}
int max_towers(int l, int r, int d)
{
  return querylist(1, 0, n-1, l, r, d);
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 10072 KB Output is correct
3 Correct 7 ms 10072 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 6 ms 10072 KB Output is correct
6 Correct 7 ms 10072 KB Output is correct
7 Incorrect 6 ms 10072 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 10072 KB Output is correct
3 Correct 7 ms 10072 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 6 ms 10072 KB Output is correct
6 Correct 7 ms 10072 KB Output is correct
7 Incorrect 6 ms 10072 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 14748 KB Output is correct
2 Correct 877 ms 30576 KB Output is correct
3 Correct 798 ms 30788 KB Output is correct
4 Correct 842 ms 30668 KB Output is correct
5 Correct 788 ms 30732 KB Output is correct
6 Correct 857 ms 30580 KB Output is correct
7 Correct 802 ms 30668 KB Output is correct
8 Correct 759 ms 30568 KB Output is correct
9 Correct 712 ms 30668 KB Output is correct
10 Correct 763 ms 30668 KB Output is correct
11 Correct 742 ms 30636 KB Output is correct
12 Correct 147 ms 30668 KB Output is correct
13 Correct 142 ms 30732 KB Output is correct
14 Correct 150 ms 30920 KB Output is correct
15 Correct 90 ms 30740 KB Output is correct
16 Correct 99 ms 30664 KB Output is correct
17 Correct 141 ms 30320 KB Output is correct
18 Correct 153 ms 30668 KB Output is correct
19 Correct 155 ms 30716 KB Output is correct
20 Correct 151 ms 30636 KB Output is correct
21 Correct 139 ms 30736 KB Output is correct
22 Correct 140 ms 30588 KB Output is correct
23 Correct 151 ms 30668 KB Output is correct
24 Correct 91 ms 30664 KB Output is correct
25 Correct 91 ms 30672 KB Output is correct
26 Correct 100 ms 30668 KB Output is correct
27 Correct 95 ms 30668 KB Output is correct
28 Correct 6 ms 10072 KB Output is correct
29 Correct 6 ms 10072 KB Output is correct
30 Correct 6 ms 10072 KB Output is correct
31 Correct 5 ms 10072 KB Output is correct
32 Correct 6 ms 10072 KB Output is correct
33 Correct 6 ms 9816 KB Output is correct
34 Correct 6 ms 10072 KB Output is correct
35 Correct 8 ms 10072 KB Output is correct
36 Correct 7 ms 10068 KB Output is correct
37 Correct 7 ms 10072 KB Output is correct
38 Correct 6 ms 10072 KB Output is correct
39 Correct 6 ms 10180 KB Output is correct
40 Correct 5 ms 10072 KB Output is correct
41 Correct 5 ms 10072 KB Output is correct
42 Correct 9 ms 10072 KB Output is correct
43 Correct 6 ms 10072 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 10072 KB Output is correct
3 Correct 7 ms 10072 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 6 ms 10072 KB Output is correct
6 Correct 7 ms 10072 KB Output is correct
7 Incorrect 6 ms 10072 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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