Submission #391994

#	Time	Username	Problem	Language	Result	Execution time	Memory
391994		nicolaalexandra	Hotel (CEOI11_hot)	C++14	100 / 100	1146 ms	33844 KiB

hot

#include <bits/stdc++.h>
#define DIM 500010
using namespace std;

pair <int,int> v[DIM],w[DIM];
vector <int> d;
int aint[DIM*4];
int n,m,nr,i,sol;

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod] = v[st].second;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

void query (int nod, int st, int dr, int val){

    if (st == dr){
        sol = st;
        return;
    }

    int mid = (st+dr)>>1;
    if (aint[nod<<1] >= val)
        query (nod<<1,st,mid,val);
    else query ((nod<<1)|1,mid+1,dr,val);
}

void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = val;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

inline int cmp (pair <int,int> a, pair <int,int> b){
    if (a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>nr;
    for (i=1;i<=n;i++)
        cin>>v[i].first>>v[i].second;

    for (i=1;i<=m;i++)
        cin>>w[i].first>>w[i].second;

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

    build (1,1,n);

    sort (w+1,w+m+1,cmp);

    for (i=1;i<=m;i++){

        if (aint[1] < w[i].second)
            continue;

        sol = 0;
        query (1,1,n,w[i].second);

        if (sol && v[sol].first < w[i].first){

            d.push_back(w[i].first - v[sol].first);

            update (1,1,n,sol,0);
        }
    }

    sort (d.begin(),d.end());

    long long ans = 0;
    for (i=d.size()-1;i>=0;i--){
        ans += d[i];
        nr--;
        if (!nr)
            break;
    }

    cout<<ans;


    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10