# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
785303 | devariaota | Global Warming (CEOI18_glo) | C++17 | 206 ms | 28916 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |