oj.uz

Submission #469236

# Submission time Handle Problem Language Result Execution time Memory
469236 2021-08-31T08:18:01 Z AmirrezaM LIS (INOI20_lis) C++17
20 / 100
 4000 ms 76932 KB 
#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")

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];

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

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){
  while(1){
	set<int>::iterator iter = lit[lis[id]].lower_bound(id);
	if(iter != lit[lis[id]].end() and a[*iter] > a[id]){
	  int jd = *iter;
	  lit[lis[id]].erase(iter);
	  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){
	  set<int>::iterator iter = lit[lis[id]].lower_bound(id);
	  if(iter != lit[lis[id]].begin() and a[*prev(iter)] < a[id]) lis[id]++;
	  else break;
	}
	upd(id);
	cout << ans << endl;
  }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Correct 13 ms 8720 KB Output is correct
4 Correct 12 ms 8748 KB Output is correct
5 Correct 26 ms 8832 KB Output is correct
6 Correct 17 ms 8828 KB Output is correct
7 Correct 16 ms 8780 KB Output is correct
8 Correct 18 ms 8780 KB Output is correct
9 Correct 15 ms 8712 KB Output is correct
10 Correct 14 ms 8772 KB Output is correct
11 Correct 15 ms 8812 KB Output is correct
12 Correct 14 ms 8752 KB Output is correct
13 Correct 20 ms 8776 KB Output is correct
14 Correct 16 ms 8780 KB Output is correct
15 Correct 15 ms 8780 KB Output is correct
16 Correct 16 ms 8780 KB Output is correct
17 Correct 18 ms 8848 KB Output is correct
18 Correct 16 ms 8780 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8652 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Correct 13 ms 8720 KB Output is correct
4 Correct 12 ms 8748 KB Output is correct
5 Correct 26 ms 8832 KB Output is correct
6 Correct 17 ms 8828 KB Output is correct
7 Correct 16 ms 8780 KB Output is correct
8 Correct 18 ms 8780 KB Output is correct
9 Correct 15 ms 8712 KB Output is correct
10 Correct 14 ms 8772 KB Output is correct
11 Correct 15 ms 8812 KB Output is correct
12 Correct 14 ms 8752 KB Output is correct
13 Correct 20 ms 8776 KB Output is correct
14 Correct 16 ms 8780 KB Output is correct
15 Correct 15 ms 8780 KB Output is correct
16 Correct 16 ms 8780 KB Output is correct
17 Correct 18 ms 8848 KB Output is correct
18 Correct 16 ms 8780 KB Output is correct
19 Correct 751 ms 21908 KB Output is correct
20 Correct 698 ms 21916 KB Output is correct
21 Correct 800 ms 21844 KB Output is correct
22 Correct 841 ms 22012 KB Output is correct
23 Correct 773 ms 21964 KB Output is correct
24 Correct 779 ms 22008 KB Output is correct
25 Correct 769 ms 21956 KB Output is correct
26 Correct 789 ms 21976 KB Output is correct
27 Correct 799 ms 21956 KB Output is correct
28 Correct 805 ms 21936 KB Output is correct
29 Correct 806 ms 21968 KB Output is correct
30 Correct 816 ms 21984 KB Output is correct
31 Correct 1077 ms 22016 KB Output is correct
32 Correct 1105 ms 21980 KB Output is correct
33 Correct 973 ms 21952 KB Output is correct
34 Correct 949 ms 22084 KB Output is correct
35 Correct 935 ms 22160 KB Output is correct
36 Correct 935 ms 22004 KB Output is correct
37 Correct 929 ms 21956 KB Output is correct
38 Correct 1002 ms 22068 KB Output is correct
39 Correct 1052 ms 22108 KB Output is correct
40 Correct 966 ms 22108 KB Output is correct
41 Correct 580 ms 19076 KB Output is correct
42 Correct 101 ms 10632 KB Output is correct
43 Correct 610 ms 18848 KB Output is correct
44 Correct 447 ms 15860 KB Output is correct
45 Correct 60 ms 9728 KB Output is correct
46 Correct 16 ms 8868 KB Output is correct
47 Correct 256 ms 13456 KB Output is correct
48 Correct 185 ms 12120 KB Output is correct
49 Correct 45 ms 9472 KB Output is correct
50 Correct 17 ms 8908 KB Output is correct
51 Correct 165 ms 11688 KB Output is correct
52 Correct 490 ms 17240 KB Output is correct
53 Correct 385 ms 15940 KB Output is correct
54 Correct 347 ms 15060 KB Output is correct
55 Correct 82 ms 10200 KB Output is correct
56 Correct 339 ms 13892 KB Output is correct
57 Correct 139 ms 11128 KB Output is correct
58 Correct 121 ms 10736 KB Output is correct
59 Correct 36 ms 9184 KB Output is correct
60 Correct 515 ms 16420 KB Output is correct
61 Correct 12 ms 8780 KB Output is correct
62 Correct 226 ms 12512 KB Output is correct
63 Correct 118 ms 10672 KB Output is correct
64 Correct 353 ms 14200 KB Output is correct
65 Correct 299 ms 13552 KB Output is correct
66 Correct 79 ms 9924 KB Output is correct
67 Correct 238 ms 12632 KB Output is correct
68 Correct 154 ms 11200 KB Output is correct
69 Correct 293 ms 13476 KB Output is correct
70 Correct 68 ms 9796 KB Output is correct
71 Execution timed out 4057 ms 76932 KB Time limit exceeded
72 Halted 0 ms 0 KB -