제출 #785286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785286		andecaandeci	Global Warming (CEOI18_glo)	C++17	0 / 100	216 ms	19204 KiB

glo

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL par[200005];
LL root(LL x)
{
  if(par[x]==x)return x;
  return par[x]=root(par[x]);
}
bool join(LL a,LL b)
{
  LL pa=root(a),pb=root(b);
  if(pa==pb)return 0;
  par[pa]=pb;
  return 1;
}
int main()
{
  LL n,x;
  scanf("%lld %lld",&n,&x);
  LL arr[n+5];
  for(LL a=1;a<=n;a++)
  {
    scanf("%lld",&arr[a]);
  }
  LL dp[n+5]; // LIS pakai indeks sekarang
  LL dp2[n+5]; //LIS sampai ke indeks sekarang
  priority_queue<LL>pq[2005];
  map<LL,LL>mp;
  multiset<LL>s;
  dp2[0]=0;
  for(LL a=1;a<=n;a++)
  {
  //  printf("a=%lld\n",a);
    if(s.empty())
    {
      s.insert(arr[a]);
      pq[1].push(arr[a]);
      
      dp[a]=1,dp[2]=1;
    } 
    else
    {
      auto jeje =s.lower_bound(arr[a]);
      auto temp=jeje;
      jeje--;
    //  for(LL a:s)cout<<a;
    //  cout<<endl;
      if(jeje==temp)
      {
        s.insert(arr[a]);
      //  printf("MASUK\n");
        pq[1].push(arr[a]);
        while(pq[1].size()>1)
        {
          LL jeje=pq[1].top();
          pq[1].pop();
          s.erase(s.find(jeje));
        }
        dp[a]=1,dp2[a]=1;
      }
      else
      {
        s.insert(arr[a]);
        join(mp[*jeje],a);
        LL sim=dp[mp[*jeje]];
        pq[sim+1].push(arr[a]);
        while(pq[sim+1].size()>1)
        {
          LL jeje=pq[sim+1].top();
          pq[sim+1].pop();
          s.erase(s.find(jeje));
        }
        dp[a]=sim+1;
      }
    }
    mp[arr[a]]=a;
    dp2[a]=max(dp2[a-1],dp[a]);
  }
  cout<<dp2[n];
}

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

glo.cpp: In function 'int main()':
glo.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld %lld",&n,&x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
glo.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%lld",&arr[a]);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25