Submission #469244

#	Time	Username	Problem	Language	Result	Execution time	Memory
469244		AmirrezaM	LIS (INOI20_lis)	C++17	20 / 100	4090 ms	77324 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define vc vector
#define pb push_back
#define fr first
#define sc second

#define Heh ios::sync_with_stdio(false) , cin.tie(0)

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

const int MAXN = 1e6 + 16 , s = 1 << 20 , sq = 1.5e3 + 15.3;

int n , b[MAXN] , a[MAXN] , it[MAXN] , lis[MAXN] , ans;
set<int> lit[sq];
set<int>::iterator iter;

int segTree[s<<1] , lazy[s<<1];

inline void shift(int v){
  segTree[v<<1] += lazy[v];
  segTree[(v<<1)^1] += lazy[v];
  lazy[v<<1] += lazy[v];
  lazy[(v<<1)^1] += lazy[v];
  lazy[v] = 0;
}
int get(int v , int tl , int tr){
  if(tl == tr) return tl;
  shift(v);
  int mid = (tl + tr) >> 1;
  if(segTree[(v<<1)^1] == 0) return get((v<<1)^1 , mid+1 , tr);
  return get((v<<1) , tl , mid);
}
void upd(int v , int tl , int tr , int l , int r , int x){
  if(l > tr or r < tl) return;
  if(l <= tl and r >= tr){
	segTree[v] += x;
	lazy[v] += x;
	return;
  }
  shift(v);
  int mid = (tl + tr) >> 1;
  upd(v<<1 , tl , mid , l , r , x);
  upd((v<<1)^1 , mid+1 , tr , l , r , x);
  segTree[v] = min(segTree[v<<1] , segTree[(v<<1)^1]);
}

void upd(int id){
  set<int>::iterator iter = lit[lis[id]].lower_bound(id);
  while(1){
	if(iter != lit[lis[id]].end() and a[*iter] > a[id]){
	  int jd = *iter;
	  iter++;
	  lit[lis[id]].erase(jd);
	  lis[jd]++;
	  upd(jd);
	}
	else break;
  }
  lit[lis[id]].insert(id);
  ans = max(ans , lis[id]);
}

int main(){
  Heh;
  for(int i = 0 ; i < (s<<1) ; i++) segTree[i] = MAXN;
  
  cin >> n;
  for(int i = 0 ; i < n ; i++){
	int id;
	cin >> id >> b[i];
	id--;
	segTree[s+i] = i-id;
  }
  for(int i = s-1 ; i >= 1 ; i--){
	segTree[i] = min(segTree[i<<1] , segTree[(i<<1)^1]);
  }

  for(int i = 0 ; i < n ; i++){
	int id = get(1 , 0 , s-1);
	a[n-i-1] = b[id];
	it[id] = n-i-1;
	upd(1 , 0 , s-1 , id , n-1 , -1);
	upd(1 , 0 , s-1 , id , id , MAXN);
  }
  
  for(int i = 0 ; i < n ; i++){
	int id = it[i];
	lis[id] = 1;
	while(1){
	  iter = lit[lis[id]].lower_bound(id);
	  if(iter != lit[lis[id]].begin() and a[*(--iter)] < a[id]) lis[id]++;
	  else break;
	}
	upd(id);
	cout << ans << endl;
  }
}

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