Submission #469210

#TimeUsernameProblemLanguageResultExecution timeMemory
469210MilladLIS (INOI20_lis)C++14
100 / 100
2590 ms217964 KiB
/// In the name of god #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef int ll; typedef long double ld; typedef pair<ll, ll> pll; const ll maxn = 1e6 + 5; ll q, x[maxn], p[maxn], b[maxn], ind[maxn], seg[maxn * 4], dp[maxn], lis; set <ll> A[maxn], B[maxn]; vector <ll> Qu; inline ll get_ind(ll id, ll ps = 0, ll v = 1, ll s = 0, ll e = q){ if(e - s == 1){ seg[v] = 1; return s; } ll mid = (e + s) >> 1, lc = v << 1, rc = lc | 1, ind; if(ps + (mid - s) - seg[lc] < id)ind = get_ind(id, ps + (mid - s) - seg[lc], rc, mid, e); else ind = get_ind(id, ps, lc, s, mid); seg[v] = seg[lc] + seg[rc]; return ind; } int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> q; for(ll i = 0; i < q; i ++)cin >> p[i] >> x[i]; for(ll i = q - 1; i >= 0; i --){ ind[i] = get_ind(p[i]); b[ind[i]] = x[i]; } set<ll>::iterator pnt; for(ll i = 0; i < q; i ++){ ll id = ind[i], d = 0; A[x[i]].insert(id); for(ll j = 1; j < x[i]; j ++){ if(A[j].empty())continue; if(*A[j].begin() > id)continue; if(*A[j].rbegin() < id){ d = max(d, dp[*A[j].rbegin()]); continue; } pnt = A[j].upper_bound(id); pnt --; d = max(d, dp[*pnt]); } d ++; dp[id] = d; B[d].insert(id); Qu.pb(id); lis = max(lis, d); while(Qu.size()){ ll id2 = Qu.back(); Qu.pop_back(); pnt = B[dp[id2]].lower_bound(id2); vector <ll> vec; while(true){ pnt ++; if(pnt == B[dp[id2]].end())break; if(b[*pnt] < b[id2])break; if(b[*pnt] == b[id2])break; vec.pb(*pnt); } for(ll j : vec){ B[dp[j]].erase(j); dp[j] ++; lis = max(lis, dp[j]); B[dp[j]].insert(j); Qu.pb(j); } } cout << lis << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...