Submission #632894

#TimeUsernameProblemLanguageResultExecution timeMemory
632894MohammadAghilLIS (INOI20_lis)C++17
0 / 100
23 ms1360 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 ptr, stk[maxn], en; int main(){ IOS(); cin >> n; stk[0] = -1; rep(i,1,n+1){ fen[i] = i&-i; stk[i] = -1; } // 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++; vector<bool> is(n + 1); 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++; assert(!is[ps]); is[ps] = true; // er(nw); val[ps] = 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]); 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}; stk[en++] = p; // stk.reserve(100); while(ptr < en){ int r = stk[ptr]; ptr++; ans = max(ans, dp[r]); auto it = place[dp[r]].lower_bound(r); for(it++; it != end(place[dp[r]]) && val[*it] > val[r];){ dp[*it]++; stk[en++] = *it; place[dp[r] + 1].insert(*it); it++; place[dp[r]].erase(prev(it)); } } cout << ans << '\n'; } return 0-0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...