| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 469205 |
2021-08-31T06:13:23 Z |
Millad |
LIS (INOI20_lis) |
C++14 |
|
49 ms |
94284 KB |
/// In the name of god
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
const ll maxn = 1e6 + 5;
ll q, x[maxn], p[maxn], b[maxn], ind[maxn], seg[maxn * 4], dp[maxn], lis;
set <ll> A[maxn], B[maxn];
vector <ll> Qu;
inline ll get_ind(ll id, ll ps = 0, ll v = 1, ll s = 0, ll e = q){
if(e - s == 1){
seg[v] = 1;
return s;
}
ll mid = (e + s) >> 1, lc = v << 1, rc = lc | 1, ind;
if(ps + (mid - s) - seg[lc] < id)ind = get_ind(id, ps + (mid - s) - seg[lc], rc, mid, e);
else ind = get_ind(id, ps, lc, s, mid);
seg[v] = seg[lc] + seg[rc];
return ind;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> q;
for(ll i = 0; i < q; i ++)cin >> p[i] >> x[i];
for(ll i = q - 1; i >= 0; i --){
ind[i] = get_ind(p[i]);
b[ind[i]] = x[i];
}
set<ll>::iterator pnt;
for(ll i = 0; i < q; i ++){
ll id = ind[i], d = 1;
A[x[i]].insert(id);;
for(ll j = 1; j < x[i]; j ++){
if(A[j].empty())continue;
if(*A[j].begin() > id)continue;
if(*A[j].rbegin() < id){
d = max(d, dp[*A[j].rbegin()]);
continue;
}
pnt = A[j].upper_bound(id);
pnt --; d = max(d, dp[*pnt] + 1);
}
dp[id] = d; B[d].insert(id);
Qu.pb(id); lis = max(lis, d);
while(Qu.size()){
ll id2 = Qu.back(); Qu.pop_back();
pnt = B[dp[id2]].lower_bound(id2);
vector <ll> vec;
while(true){
pnt ++;
if(pnt == B[dp[id2]].end())break;
if(b[*pnt] < b[id2])break;
if(b[*pnt] == b[id2])continue;
vec.pb(*pnt);
}
for(ll j : vec){
B[dp[j]].erase(j);
dp[j] ++; lis = max(lis, dp[j]);
B[dp[j]].insert(j); Qu.pb(j);
}
}
cout << lis << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
