Submission #72064

#	Time	Username	Problem	Language	Result	Execution time	Memory
72064		마릴린 희정 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	230 ms	13552 KiB

box

#include<bits/stdc++.h>
using namespace std;
int N;
int H[1010101];
int ans[1010101];

struct doublepq
{
  priority_queue<int> PQ1, PQ2;
  void insert(int x)
  {
    PQ1.push(x);
  }
  void proc()
  {
    while(!PQ1.empty() && !PQ2.empty() && PQ1.top() == PQ2.top())
    {
      PQ1.pop(); PQ2.pop();
    }
  }
  int top()
  {
    proc(); return PQ1.top();
  }
  void erase(int v)
  {
    PQ2.push(v);
  }
} PQ;

int main()
{
  scanf("%d", &N);
  for(int i=0; i<N; ++i) scanf("%d", H+i);
  H[N] = (int)1e9+1;
  
  int from = 0, to = 0;
  //multiset<int> S; S.insert(H[0]);
  PQ.insert(H[0]);
  for(int t=0; t<N; ++t)
  {
    while(PQ.top() >= H[to+1])
    {
      PQ.insert(H[++to]);
      PQ.erase(H[from++]);
    }
    ans[t] = to+1;
    if(from == 0)
      PQ.insert(H[++to]);
    else
      PQ.insert(H[--from]);
  }
  for(int i=0; i<N; ++i)
    if(ans[i] == N) printf("-1 ");
    else printf("%d ", ans[i]-i);
  puts("");
  return 0;
}

Compilation message (stderr)

box.cpp: In function 'int main()':
box.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
box.cpp:34:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0; i<N; ++i) scanf("%d", H+i);
                          ~~~~~^~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 83 / 83