Submission #284336

#	Time	Username	Problem	Language	Result	Execution time	Memory
284336		Alexa2001	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	341 ms	16368 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

int A[Nmax], B[Nmax], C[Nmax], D[Nmax], ans[Nmax];
vector<int> as;

int n, q;


class AIB
{
    int a[Nmax];

    int ub(int x)
    {
        return (x&(-x));
    }

public:
    int query(int x)
    {
        x = lower_bound(as.begin(), as.end(), x) - as.begin() + 1;

        int ans = 0;
        for(; x<=n; x+=ub(x))
            ans = max(ans, a[x]);
        return ans;
    }

    void update(int pos, int val)
    {
        pos = lower_bound(as.begin(), as.end(), pos) - as.begin() + 1;

        for(; pos; pos-=ub(pos))
            a[pos] = max(a[pos], val);
    }
} aib;

void add(int x)
{
    int res = aib.query(x);
    aib.update(x, res+1);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> q;

    int i;

    for(i=1; i<=n; ++i) cin >> A[i] >> B[i];
    for(i=1; i<=q; ++i) cin >> C[i] >> D[i];

    vector<int> ord1(n), ord2(q);
    iota(ord1.begin(), ord1.end(), 1);
    iota(ord2.begin(), ord2.end(), 1);

    sort(ord1.begin(), ord1.end(), [] (int x, int y) { if(B[x] == B[y]) return A[x] > A[y]; return B[x] < B[y]; } );
    sort(ord2.begin(), ord2.end(), [] (int x, int y) { return D[x] < D[y]; } );

    for(i=1; i<=n; ++i) as.push_back(A[i]);
    sort(as.begin(), as.end());
    as.erase( unique(as.begin(), as.end()), as.end() );

    i = 0;
    for(auto id : ord2)
    {
        while(i < n && B[ord1[i]] <= D[id])
            add(A[ord1[i]]), ++i;

        ans[id] = aib.query(C[id]);
    }

    for(i=1; i<=q; ++i) cout << ans[i] << '\n';

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49