Submission #1019090

#TimeUsernameProblemLanguageResultExecution timeMemory
1019090ivazivaGlobal Warming (CEOI18_glo)C++14
15 / 100
65 ms7048 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 200010 long long n,x; long long a[MAXN],b[MAXN]; long long lis1[MAXN],lis2[MAXN]; vector<long long> dp; int main() { cin>>n>>x; for (long long i=1;i<=n;i++) cin>>a[i]; for (long long i=1;i<=n;i++) { long long pos=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();lis1[i]=pos+1; if (pos==dp.size()) dp.push_back(a[i]); else dp[pos]=a[i]; } dp.clear(); for (long long i=n;i>=1;i--) { long long pos1=lower_bound(dp.begin(),dp.end(),x-a[i])-dp.begin();lis2[i]=pos1+1; long long pos2=lower_bound(dp.begin(),dp.end(),a[i]*(-1))-dp.begin(); if (pos2==dp.size()) dp.push_back(a[i]*(-1)); else dp[pos2]=a[i]; } long long ans=lis1[n]; for (long long i=1;i<n;i++) { long long lis=lis1[i]+lis2[i]-1; ans=max(ans,lis); } cout<<ans<<endl; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:19:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if (pos==dp.size()) dp.push_back(a[i]);
      |             ~~~^~~~~~~~~~~
glo.cpp:27:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (pos2==dp.size()) dp.push_back(a[i]*(-1));
      |             ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...