Submission #785303

#	Time	Username	Problem	Language	Result	Execution time	Memory
785303		devariaota	Global Warming (CEOI18_glo)	C++17	10 / 100	206 ms	28916 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]);
  }
  if(!x)
  {
    LL dp[n+5]; // LIS pakai indeks sekarang
    LL dp2[n+5]; //LIS sampai ke indeks sekarang
    priority_queue<LL>pq[200005];
    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]);
    }
    
  //  for(LL a=1;a<=n;a++)
  //  {
  //    cout<<dp[a]<<" "<<dp2[a]<<endl;
  //  }
    cout<<dp2[n];
  }
  
}

Compilation message (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: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25