Submission #1068776

#TimeUsernameProblemLanguageResultExecution timeMemory
1068776PotatoTheWarriorFRTTGlobal Warming (CEOI18_glo)C++14
10 / 100
24 ms4720 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll p1 = 27644437; ll p2 = 1000000007; int LIS(int n, int a[]) { ll dp[n+1]; // dp[l] = smallest element at which a sequence of size l ends; for(int i=1;i<=n;i++) { dp[i] = LONG_LONG_MAX; } int ans = 1; dp[1] = a[0]; for(int i=1;i<n;i++) { if(dp[ans] < a[i]) { ans++; dp[ans] = a[i]; }else if(a[i] < dp[1]) { dp[1] = a[i]; }else{ int r = ans; int l = 1; while(r - l > 1) { int m = (r+l)/2; if(a[i] < dp[m]) { r = m; }else if(a[i] >= dp[m]) { l = m; } } dp[r] = a[i]; } } return ans; } void solve() { int n, x; cin >> n >> x; int a[n+1]; for(int i=0;i<n;i++) { cin >> a[i]; } if(x == 0) { cout << LIS(n, a) << endl; }else{ cout << 0 << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); char dksfjn; cin >> dksfjn; }
#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...