Submission #1188364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188364		DangKhoizzzz	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	370 ms	58356 KiB

matryoshka

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e9;
const int maxn = 2e5 + 7;
const int maxv = 8e5 + 7;

struct Fenwick_Tree
{
    int bit[maxv];

    void update(int pos , int val)
    {
        while(pos < maxv)
        {
            bit[pos] = max(bit[pos] , val);
            pos += (pos & (-pos));
        }
    }

    int get(int pos)
    {
        int res = 0;
        while(pos > 0)
        {
            res = max(res , bit[pos]);
            pos -= (pos & (-pos));
        }
        return res;
    }
} BIT;


int n , q , r[maxn] , h[maxn] , ans[maxn];
pii ask[maxn];
vector <int> v[maxv];
vector <int> query[maxv];

void compress()
{
    vector <int> val;
    for(int i = 1; i <= n; i++)
    {
        val.push_back(r[i]);
        val.push_back(h[i]);
    }
    for(int i = 1; i <= q; i++)
    {
        val.push_back(ask[i].fi);
        val.push_back(ask[i].se);
    }
    sort(val.begin() , val.end());
    val.erase(unique(val.begin() , val.end()) , val.end());
    for(int i = 1; i <= n; i++)
    {
        r[i] = upper_bound(val.begin() , val.end() , r[i]) - val.begin();
        h[i] = upper_bound(val.begin() , val.end() , h[i]) - val.begin();
    }
    for(int i = 1; i <= q; i++)
    {
        ask[i].fi = upper_bound(val.begin() , val.end() , ask[i].fi) - val.begin();
        ask[i].se = upper_bound(val.begin() , val.end() , ask[i].se) - val.begin();
    }

    //for(int i = 1; i <= n; i++) cout << r[i] << ' ' << h[i] << '\n';
    //for(int i = 1; i <= q; i++) cout << ask[i].fi << ' ' << ask[i].se << '\n';
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> r[i] >> h[i];
    for(int i = 1; i <= q; i++)
    {
        cin >> ask[i].fi >> ask[i].se;
    }
    compress();

    for(int i = 1; i <= n; i++)
    {
        v[r[i]].push_back(h[i]);
    }
    for(int i = 1; i < maxv; i++)
    {
        sort(v[i].begin() , v[i].end());
    }
    for(int i = 1; i <= q; i++)
    {
        query[ask[i].fi].push_back(i);
    }

    for(int i = maxv - 1; i > 0; i--)
    {
        for(int x: v[i])
        {
            BIT.update(x , BIT.get(x) + 1);
        }

        for(int x: query[i])
        {
            ans[x] = BIT.get(ask[x].se);
        }
    }

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    //cin >> t;
    t = 1;
    while(t--)
    {
        solve();
    }
    return 0;
}

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