oj.uz

Submission #391994

# Submission time Handle Problem Language Result Execution time Memory
391994 2021-04-20T09:38:22 Z nicolaalexandra Hotel (CEOI11_hot) C++14
100 / 100
 1146 ms 33844 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 588 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1660 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 2768 KB Output is correct
2 Correct 103 ms 2424 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 6540 KB Output is correct
2 Correct 233 ms 4236 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 12920 KB Output is correct
2 Correct 832 ms 26188 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1053 ms 14436 KB Output is correct
2 Correct 1146 ms 33844 KB Output is correct
3 Correct 1104 ms 30868 KB Output is correct