oj.uz

Submission #391992

# Submission time Handle Problem Language Result Execution time Memory
391992 2021-04-20T09:27:58 Z nicolaalexandra Hotel (CEOI11_hot) C++14
20 / 100
 855 ms 28436 KB 
#include <bits/stdc++.h>
#define DIM 500010
using namespace std;

pair <int,int> v[DIM],w[DIM];
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);

    long long ans = 0;
    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){
            ans += w[i].first - v[sol].first;

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

            nr--;
            if (!nr)
                break;
        }
    }

    cout<<ans;


    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 860 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 2992 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 5084 KB Output is correct
2 Incorrect 106 ms 3876 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 13088 KB Output is correct
2 Incorrect 206 ms 6836 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 804 ms 25988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 855 ms 28436 KB Output isn't correct
2 Halted 0 ms 0 KB -