Submission #632813

#TimeUsernameProblemLanguageResultExecution timeMemory
632813MohammadAghilLIS (INOI20_lis)C++17
0 / 100
390 ms1048576 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, lg = 30, 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 seg[maxn<<2], n, pos[maxn], val[maxn], dp[maxn], tmp[maxn]; set<int> val_pos[maxn], place[maxn]; void build(int x = 1, int lx = 0, int rx = n){ if(lx + 1 == rx){ seg[x] = 1; return; } int mid = (lx + rx)>>1; build(x<<1, lx, mid); build(x<<1|1, mid, rx); seg[x] = rx - lx; } int get(int k, int x = 1, int lx = 0, int rx = n){ seg[x]--; if(lx + 1 == rx){ return lx; } int mid = (lx + rx)>>1; if(seg[x<<1] < k) return get(k - seg[x<<1], x<<1|1, mid, rx); return get(k, x<<1, lx, mid); } int main(){ IOS(); cin >> n; build(); rep(i,0,n){ cin >> pos[i] >> tmp[i]; } per(i,n-1,0) { int nw = get(pos[i]); // er(nw); val[nw] = tmp[i]; pos[i] = nw; } // 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,1,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]].upper_bound(r); 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(bg, en); place[dp[r]].erase(bg, en); } cout << ans << '\n'; } return 0-0; }

Compilation message (stderr)

Main.cpp: In function 'void IOS()':
Main.cpp:19:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |           freopen("in.txt", "r", stdin);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |           freopen("out.txt", "w", stdout);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...