| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 236698 |
2020-06-02T23:56:16 Z |
Mercenary |
Hotel (CEOI11_hot) |
C++14 |
|
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);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
1792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
7800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
14232 KB |
Output is correct |
| 2 |
Correct |
87 ms |
9840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
533 ms |
34532 KB |
Output is correct |
| 2 |
Correct |
199 ms |
23672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
634 ms |
68624 KB |
Output is correct |
| 2 |
Correct |
553 ms |
68720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
