| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 468945 |
2021-08-30T09:10:31 Z |
Millad |
LIS (INOI20_lis) |
C++14 |
|
1 ms |
332 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 long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
const ll maxn = 2e6 + 5;
ll q, p[maxn], x[maxn], x2[maxn], ind[maxn], seg[maxn * 4];
set<ll> st;
ll find_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 = 0;
if(ps + (mid - s) - seg[lc] < id)ind = find_ind(id, ps + (mid - s) - seg[lc], rc, mid, e);
else ind = find_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] = find_ind(p[i]);
x2[ind[i]] = x[i];
}
st.insert(ind[0]); cout << 1 << '\n';
for(ll i = 1; i < q; i ++){
if(ind[i] < *st.begin()){
if(x[i] < x2[*st.begin()])st.insert(ind[i]);
}
else if(ind[i] > *st.rbegin()){
if(x[i] > x2[*st.rbegin()])st.insert(ind[i]);
}
else{
auto pnt = st.lower_bound(ind[i]);
if(x[i] < x2[*pnt]){
pnt --;
if(x[i] > x2[*pnt])st.insert(ind[i]);
}
}
cout << st.size() << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
