oj.uz

Submission #828581

# Submission time Handle Problem Language Result Execution time Memory
828581 2023-08-17T11:58:56 Z Amylopectin Radio Towers (IOI22_towers) C++17
0 / 100
 583 ms 50208 KB 
#include "towers.h"
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mxn = 2e6 + 10,mxi = 2e9 + 10;
int n,he[mxn] = {},of,qsu[mxn] = {},sem[mxn] = {},fro[mxn] = {},bac[mxn] = {};
vector<int> se[mxn] = {};
int bui(int cl,int cr,int no)
{
  if(cl == cr)
  {
    sem[no] = he[cl];
    return 0;
  }
  int mid = (cl+cr) / 2;
  bui(cl,mid,no*2);
  bui(mid+1,cr,no*2+1);
  sem[no] = min(sem[no*2],sem[no*2+1]);
  return 0;
}
int fii(int cl,int cr,int no,int tl,int tr)
{
  if(cl > tr || cr < tl)
  {
    return mxi;
  }
  if(cl >= tl && cr <= tr)
  {
    return sem[no];
  }
  int mid = (cl+cr) / 2;
  return min(fii(cl,mid,no*2,tl,tr),fii(mid+1,cr,no*2+1,tl,tr));
}
void init(int N, std::vector<int> H) 
{
  int i,j,cn,cm,fn,fm;
  n = N;
  for(i=0; i<n; i++)
  {
    he[i] = H[i];
  }
   of = 0;
   bui(0,n-1,1);
  return ;
}

int max_towers(int cl, int cr, int d) 
{
  int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
  if(of== 0)
  {
    for(i=0; i<n; i++)
    {
      if(cmi == -1)
      {
        cmi = he[i];
      }
      else 
      {
        cmi = min(cmi,he[i]);
      }
      if(he[i] - cmi >= d && beh - cmi >= d)
      {
        cou ++;
        beh = he[i];
        cmi = -1;
        qsu[i] ++;
      }
      else 
      {
        if(he[i] > beh)
        {
          beh = he[i];
          cmi = -1;
        }
      }
    }
    if(cmi != -1 && beh - cmi >= d)
    {
      cou ++;
    }
    be = -1;
    for(i=0; i<n; i++)
    {
      if(qsu[i] == 1)
      {
        be = i;
        bac[i] = i;
      }
      else 
      {
        bac[i] = be;
      }
    }
    be = -1;
    for(i=n-1; i>=0; i--)
    {
      if(qsu[i] == 1)
      {
        be = i;
        fro[i] = i;
      }
      else 
      {
        fro[i] = be;
      }
    }
    for(i=1; i<n; i++)
    {
      qsu[i] += qsu[i-1];
    }
    of = 1;
  }

  cva = qsu[cr];
  if(cl > 0)
  {
    cva -= qsu[cl-1];
  }
  if(cva == 0)
  {
    return 1;
  }
  if(he[fro[cl]] - fii(0,n-1,1,cl,fro[cl]) >= d)
  {
    cva ++;
  }
  if(he[bac[cr]] - fii(0,n-1,1,bac[cr],cr) >= d)
  {
    cva ++;
  }
  cva --;
  if(cva == 0)
  {
    return 1;
  }
  return cva;
}

Compilation message

towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:38:9: warning: unused variable 'j' [-Wunused-variable]
   38 |   int i,j,cn,cm,fn,fm;
      |         ^
towers.cpp:38:11: warning: unused variable 'cn' [-Wunused-variable]
   38 |   int i,j,cn,cm,fn,fm;
      |           ^~
towers.cpp:38:14: warning: unused variable 'cm' [-Wunused-variable]
   38 |   int i,j,cn,cm,fn,fm;
      |              ^~
towers.cpp:38:17: warning: unused variable 'fn' [-Wunused-variable]
   38 |   int i,j,cn,cm,fn,fm;
      |                 ^~
towers.cpp:38:20: warning: unused variable 'fm' [-Wunused-variable]
   38 |   int i,j,cn,cm,fn,fm;
      |                    ^~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:51:9: warning: unused variable 'j' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |         ^
towers.cpp:51:11: warning: unused variable 'cn' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |           ^~
towers.cpp:51:14: warning: unused variable 'cm' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |              ^~
towers.cpp:51:17: warning: unused variable 'fn' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |                 ^~
towers.cpp:51:20: warning: unused variable 'fm' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |                    ^~
towers.cpp:51:32: warning: unused variable 'cma' [-Wunused-variable]
   51 |   int i,j,cn,cm,fn,fm,cmi = -1,cma,beh = mxi,cou = 0,be,cva;
      |                                ^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47260 KB Output is correct
2 Correct 24 ms 47312 KB Output is correct
3 Correct 23 ms 47312 KB Output is correct
4 Correct 24 ms 47264 KB Output is correct
5 Correct 23 ms 47340 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 24 ms 47364 KB Output is correct
8 Correct 29 ms 47332 KB Output is correct
9 Correct 24 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Correct 23 ms 47284 KB Output is correct
12 Incorrect 24 ms 47212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47260 KB Output is correct
2 Correct 24 ms 47312 KB Output is correct
3 Correct 23 ms 47312 KB Output is correct
4 Correct 24 ms 47264 KB Output is correct
5 Correct 23 ms 47340 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 24 ms 47364 KB Output is correct
8 Correct 29 ms 47332 KB Output is correct
9 Correct 24 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Correct 23 ms 47284 KB Output is correct
12 Incorrect 24 ms 47212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 50208 KB 7th lines differ - on the 1st token, expected: '4389', found: '4388'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 48028 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 24 ms 47260 KB Output is correct
2 Correct 24 ms 47312 KB Output is correct
3 Correct 23 ms 47312 KB Output is correct
4 Correct 24 ms 47264 KB Output is correct
5 Correct 23 ms 47340 KB Output is correct
6 Correct 24 ms 47312 KB Output is correct
7 Correct 24 ms 47364 KB Output is correct
8 Correct 29 ms 47332 KB Output is correct
9 Correct 24 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Correct 23 ms 47284 KB Output is correct
12 Incorrect 24 ms 47212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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