제출 #1292587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292587		huutuan	LIS (INOI20_lis)	C++20	100 / 100	3877 ms	28148 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct BIT{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   int lower_bound(int val){
      int ans=0;
      for (int k=19; k>=0; --k){
         if ((ans|(1<<k))<=n && t[ans|(1<<k)]<val){
            ans|=1<<k;
            val-=t[ans];
         }
      }
      return ans+1;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans=max(ans, t[i]);
      return ans;
   }
} bit;

struct BIT2{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]=max(t[i], val);
   }
   void reset(int pos){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]=0;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans=max(ans, t[i]);
      return ans;
   }
} bit2;

const int N=1e6+10;
int n, m;
int p[N], x[N];
int ans[N];
vector<int> vals;
vector<int> vv[N];
int f[N];

int calc(int pos){
   vector<pair<int, int>> v;
   for (int i=1; i<=pos; ++i) v.emplace_back(p[i], x[i]), f[x[i]]=0;
   sort(v.begin(), v.end());
   int mx=0;
   for (auto &i:v){
      int nf=bit2.get(i.second-1)+1;
      if (nf>f[i.second]) bit2.update(i.second, nf), f[i.second]=nf;
      mx=max(mx, nf);
   }
   for (auto &i:v) bit2.reset(i.second);
   return mx;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> p[i] >> x[i], vals.push_back(x[i]);
   sort(vals.begin(), vals.end());
   vals.resize(unique(vals.begin(), vals.end())-vals.begin());
   for (int i=1; i<=n; ++i) x[i]=lower_bound(vals.begin(), vals.end(), x[i])-vals.begin()+1;
   m=vals.size();
   bit.init(n);
   for (int i=1; i<=n; ++i) bit.update(i, 1);
   for (int i=n; i>=1; --i){
      p[i]=bit.lower_bound(p[i]);
      bit.update(p[i], -1);
   }
   bit2.init(m);
   memset(ans, -1, sizeof ans);
   auto dnc=[&](auto &&self, int l, int r) -> void {
      if (ans[l]==-1) ans[l]=calc(l);
      if (ans[r]==-1) ans[r]=calc(r);
      if (l+1>=r) return;
      if (ans[l]==ans[r]){
         for (int j=l; j<=r; ++j) ans[j]=ans[l];
         return;
      }
      int mid=(l+r)>>1;
      ans[mid]=calc(mid);
      self(self, l, mid);
      self(self, mid+1, r);
   };
   dnc(dnc, 1, n);
   for (int i=1; i<=n; ++i) cout << ans[i] << '\n';
   return 0;
}

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