Submission #468943

#	Time	Username	Problem	Language	Result	Execution time	Memory
468943		Millad	LIS (INOI20_lis)	C++14	0 / 100	2 ms	332 KiB

Main

// 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 = 1e6 + 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;
        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';
        }
}

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