oj.uz

답안 #236698

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236698 2020-06-02T23:56:16 Z Mercenary Hotel (CEOI11_hot) C++14
100 / 100
 2049 ms 79608 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int n , m , o;
ii a[maxn] , b[maxn];
pair<ll,int> s[maxn * 4];
ll lz[maxn * 4];
void push(int x , bool key){
    s[x].first += lz[x];
    if(key){
        lz[x * 2] += lz[x];
        lz[x * 2 + 1] += lz[x];
    }
    lz[x] = 0;
}
void update(int x , int l , int r , int L , int R , int val){
    if(l == r)s[x].second = l;
    push(x , l != r);
    if(l > R || L > r)return;
    if(L <= l && r <= R){
        lz[x] += val;
        push(x , l != r);
        return;
    }
    int mid = l + r >> 1;
    update(x * 2 , l , mid , L , R , val);
    update(x * 2 + 1 , mid + 1 , r , L , R , val);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
}
int lim[maxn] , limh[maxn];
set<ii> ss;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m >> o;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].second >> a[i].first;
        lim[i] = m + 1;
    }
    for(int i = 1 ; i <= m ; ++i){
        cin >> b[i].second >> b[i].first;
    }
    ll res = 0;
    sort(a + 1 , a + n + 1);
    sort(b + 1 , b + m + 1);
    for(int i = 1 ; i <= m ; ++i){
        int it = lower_bound(a + 1 , a + n + 1 , mp(b[i].first , 0)) - a;
        if(it <= n)limh[it] = i , lim[it] = min(lim[it] , i) , update(1,1,m,i,i,b[i].second - a[it].second);
        else update(1,1,m,i,i,-1e9);
    }
    for(int i = 1 ; i <= n ; ++i){
        ss.insert(mp(a[i].first , i));
    }
    ss.insert(mp(1e9 + 1 , n + 1));
    a[n + 1].second = 1e9;
    lim[n + 1] = m + 1;
    for(int i = 1 ; i <= o ; ++i){
        if(s[1].first <= 0)break;
        res += s[1].first;
        int tmp = s[1].second;
        update(1,1,m,tmp,tmp,-1e9);
        auto it = ss.lower_bound(mp(b[tmp].first,0));
        auto pick = (*it).second;
        auto pick1 = (*next(it)).second;
        ss.erase(it);
        update(1 , 1 , m ,lim[pick] , limh[pick] , -a[pick1].second + a[pick].second);
        lim[pick1] = lim[pick];
        limh[pick1] = max(limh[pick1] , limh[pick]);
//        cout << tmp << " " << pick << " " << pick1 << endl;
    }
    cout << res;
}

Compilation message

hot.cpp: In function 'void update(int, int, int, int, int, int)':
hot.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
hot.cpp: In function 'int main()':
hot.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:54:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 432 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1792 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 7800 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 14232 KB Output is correct
2 Correct 87 ms 9840 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 533 ms 34532 KB Output is correct
2 Correct 199 ms 23672 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 634 ms 68624 KB Output is correct
2 Correct 553 ms 68720 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 667 ms 74920 KB Output is correct
2 Correct 1471 ms 79608 KB Output is correct
3 Correct 2049 ms 76708 KB Output is correct