Submission #632825

#TimeUsernameProblemLanguageResultExecution timeMemory
632825MohammadAghilLIS (INOI20_lis)C++17
20 / 100
4067 ms6916 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); // #ifndef ONLINE_JUDGE // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 1e6 + 5, sq = 2000, lg = 20, inf = ll(1e18) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} int fen[maxn], n, pos[maxn], val[maxn], dp[maxn], tmp[maxn]; set<int> val_pos[sq], place[sq]; int main(){ IOS(); cin >> n; rep(i,1,n+1){ fen[i] = i&-i; } map<int, int> cmp; rep(i,0,n){ cin >> pos[i] >> tmp[i]; cmp[tmp[i]] = 0; } int id = 0; for(auto&c: cmp) c.ss = id++; per(i,n-1,0) { int ps = 0, cr = pos[i]; per(i,lg-1,0){ if((ps|(1<<i)) < n && fen[ps|(1<<i)] < cr){ ps |= 1<<i; cr -= fen[ps]; } } ps++; // er(nw); val[ps] = cmp[tmp[i]]; pos[i] = ps; for(; ps < n + 1; ps += ps&-ps) fen[ps]--; } // rep(i,0,n) er(pos[i], val[i]); int ans = 1; rep(i,0,n){ int p = pos[i], v = val[pos[i]]; dp[p] = 1; rep(j,0,v){ auto it = lower_bound(all(val_pos[j]), p); if(it != begin(val_pos[j])){ dp[p] = max(dp[p], dp[*prev(it)] + 1); // er(i, j); } } // er(i, dp[p]); ans = max(ans, dp[p]); place[dp[p]].insert(p); val_pos[v].insert(p); // auto bg = place[dp[p]].upper_bound(p), en = bg; // for(; en != end(place[dp[pos[i]]]) && val[*en] > v; en++) dp[*en]++, ans = max(ans, dp[p] + 1), er(i, *en, val[*en], v); // place[dp[p] + 1].insert(bg, en); // place[dp[p]].erase(bg, en); // rep(i,1,5){ // cerr << i << ":" << endl; // for(int c: place[i]) cerr << c << ' '; // cerr << endl; // } // cerr << "_____" << endl; vector<int> stk{p}; while(sz(stk)){ int r = stk.back(); stk.pop_back(); auto bg = place[dp[r]].lower_bound(r); if(bg == end(place[dp[r]]) || *bg - r) continue; bg++; auto en = bg; for(; en != end(place[dp[r]]) && val[*en] > val[r]; en++){ dp[*en]++; ans = max(ans, dp[r] + 1); stk.pb(*en); place[dp[r] + 1].insert(*en); } place[dp[r]].erase(bg, en); } cout << ans << '\n'; } return 0-0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...