Submission #254340

#TimeUsernameProblemLanguageResultExecution timeMemory
254340MarcoMeijerGlobal Warming (CEOI18_glo)C++14
0 / 100
44 ms4284 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e18 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } //===================// // Added libraries // //===================// //===================// //end added libraries// //===================// void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 5e5; ll n, x; ll t[MX]; ll LIS[MX]; ll L[MX], m=0; void program() { IN(n,x); RE(i,n) IN(t[i]); RE(i,n) { ll lb=-1, ub=m-1; while(lb != ub) { ll mid=(lb+ub+1)/2; if(L[mid] <= t[i]) lb=mid; else ub=mid-1; } LIS[i] = lb+2; if(lb == m-1) L[m++] = INF; L[lb+1] = min(L[lb+1], t[i]); } ll ans=0; RE(i,n) ans = max(ans, LIS[i]); OUTL(ans); }
#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...