Submission #427100

#	Time	Username	Problem	Language	Result	Execution time	Memory
427100		Trickster	Exhibition (JOI19_ho_t2)	C++14	100 / 100	486 ms	46148 KiB

joi2019_ho_t2

//Suleyman Atayew

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
#define N 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

pii p[N];
int n, m, sz;
map <int, int> M;
int v[N];
pii T[N*4];
priority_queue <int> Q[N*4];

void upd(int pos, pii x, int l, int r, int node)
{
    if(l == r) {
        if(x.ff) {
            Q[node].push(x.ss);
            T[node] = {pos, Q[node].top()};
        } else {
            Q[node].pop();
            if(!Q[node].empty())
                T[node] = {pos, Q[node].top()};
            else 
                T[node] = {0, 0};
        }
        return;
    }

    if(pos <= (l+r)/2)
        upd(pos, x, l, (l+r)/2, node*2);
    else
        upd(pos, x, (l+r)/2+1, r, node*2+1);
    
    if(T[node*2].ss > T[node*2+1].ss)
        T[node] = T[node*2];
    else
        T[node] = T[node*2+1];
}

pii tap(int pos, int l, int r, int node)
{
    if(l > pos) return {0, 0};
    if(r <= pos) return {T[node].ss, T[node].ff};

    return max(tap(pos, l, (l+r)/2, node*2), tap(pos, (l+r)/2+1, r, node*2+1));
}

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);

    cin >> n >> m;

    vector <int> E;
    for(int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;

        M[a] = 1;
        p[i] = {a, b};
    }

    for(int i = 1; i <= m; i++)
        cin >> v[i], M[v[i]] = 1;

    for(auto &i: M) i.ss = ++sz;

    sort(v+1, v+1+m);

    for(int i = 1; i <= n; i++)
        upd(M[p[i].ff], {1, p[i].ss}, 1, sz, 1);

    for(int i = m; i >= 0; i--) {
        int x = M[v[i]];

        pii ans = tap(x, 1, sz, 1);

        if(ans.ss == 0 || !i) {
            cout << m-i;
            return 0;
        }

        upd(ans.ss, {0, ans.ff}, 1, sz, 1);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50