| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115632 |
2019-06-08T11:50:11 Z |
김세빈(#2868) |
Hotel (CEOI11_hot) |
C++14 |
|
1953 ms |
161284 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
struct lazyseg{
pll T[1101010];
ll L[1101010];
void init(ll p, ll s, ll e, pll *D)
{
if(s == e){
T[p] = pll(D[s].second, s);
}
else{
init(p << 1, s, s + e >> 1, D);
init(p << 1 | 1, (s + e >> 1) + 1, e, D);
T[p] = max(T[p << 1], T[p << 1 | 1]);
}
}
void spread(ll p, ll s, ll e)
{
T[p << 1].first += L[p]; L[p << 1] += L[p];
T[p << 1 | 1].first += L[p]; L[p << 1 | 1] += L[p];
L[p] = 0;
}
void add(ll p, ll s, ll e, ll l, ll r, ll v)
{
if(r < s || e < l) return;
else if(l <= s && e <= r){
T[p].first += v; L[p] += v;
return;
}
spread(p, s, e);
add(p << 1, s, s + e >> 1, l, r, v);
add(p << 1 | 1, (s + e >> 1) + 1, e, l, r, v);
T[p] = max(T[p << 1], T[p << 1 | 1]);
}
pll get_max() { return T[1]; }
};
lazyseg T;
pll H[505050], R[505050], K[505050];
set <pll> S;
ll n, m, k, ans;
int main()
{
ll i, j, v, s;
scanf("%lld%lld%lld", &n, &m, &k);
for(i=0; i<n; i++){
scanf("%lld%lld", &H[i].second, &H[i].first);
}
sort(H, H + n);
H[n] = pll(2e9, 2e9);
for(i=0; i<m; i++){
scanf("%lld%lld", &R[i].second, &R[i].first);
}
sort(R, R + m);
for(i=0, j=0; i<=n; i++){
K[i].first = j;
for(; j<m && R[j].first <= H[i].first; j++);
K[i].second = j - 1;
S.insert(pll(H[i].first, i));
}
T.init(1, 0, m - 1, R);
for(i=0; i<=n; i++){
T.add(1, 0, m - 1, K[i].first, K[i].second, -H[i].second);
}
for(s=0; k--; ){
tie(v, i) = T.get_max(); s += v;
// printf("%lld %lld\n", v, i);
T.add(1, 0, m - 1, i, i, -1e18);
auto it1 = S.lower_bound(pll(R[i].first, i)); i = it1 -> second;
auto it2 = next(it1); j = it2 -> second;
T.add(1, 0, m - 1, K[i].first, K[i].second, H[i].second - H[j].second);
K[j].first = K[i].first; S.erase(it1);
ans = max(ans, s);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
hot.cpp: In member function 'void lazyseg::init(ll, ll, ll, pll*)':
hot.cpp:18:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init(p << 1, s, s + e >> 1, D);
~~^~~
hot.cpp:19:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init(p << 1 | 1, (s + e >> 1) + 1, e, D);
~~^~~
hot.cpp: In member function 'void lazyseg::add(ll, ll, ll, ll, ll, ll)':
hot.cpp:42:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add(p << 1, s, s + e >> 1, l, r, v);
~~^~~
hot.cpp:43:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
add(p << 1 | 1, (s + e >> 1) + 1, e, l, r, v);
~~^~~
hot.cpp: In function 'int main()':
hot.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &H[i].second, &H[i].first);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &R[i].second, &R[i].first);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
17664 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
38 ms |
35192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
35192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
17664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
19064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
24540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
57208 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
726 ms |
91032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
653 ms |
72296 KB |
Output is correct |
| 2 |
Correct |
908 ms |
73468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
648 ms |
79224 KB |
Output is correct |
| 2 |
Runtime error |
1953 ms |
161284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
