Submission #632883

#	Time	Username	Problem	Language	Result	Execution time	Memory
632883		MohammadAghil	LIS (INOI20_lis)	C++17	20 / 100	4058 ms	6960 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, 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++;
     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] = 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};
          stk.reserve(100);

          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];){
                    dp[*en]++;
                    assert(dp[*en] <= *en);
                    ans = max(ans, dp[r] + 1);
                    stk.pb(*en);
                    place[dp[r] + 1].insert(*en);
                    en++;
                    place[dp[r]].erase(prev(en));
               }
          }

          cout << ans << '\n';
     }
     return 0-0;
}

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