제출 #828581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828581		Amylopectin	Radio Towers (IOI22_towers)	C++17	0 / 100	583 ms	50208 KiB

towers

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23