Submission #632814

#	Time	Username	Problem	Language	Result	Execution time	Memory
632814		MohammadAghil	LIS (INOI20_lis)	C++17	20 / 100	4049 ms	103108 KiB

Main

      #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;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80