| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117177 |
2019-06-15T07:56:21 Z |
Namnamseo |
Hotel (CEOI11_hot) |
C++17 |
|
336 ms |
32248 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
void read(pp& x){ scanf("%d%d",&x.first, &x.second); }
void read(pll& x){ scanf("%lld%lld",&x.first, &x.second); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
const int inf = int(1e9) + 10;
struct tree {
const static int M = 524288;
pp t[M<<1];
void init() {
fill(t, t+(2*M), pp(-inf, -1));
}
pp rmax(int l, int r) {
pp ret(-inf, -1);
for(l+=M, r+=M; l<=r; l/=2, r/=2) {
if(l%2==1) ret=max(ret, t[l++]);
if(r%2==0) ret=max(ret, t[r--]);
}
return ret;
}
void put(int p, pp v) {
for(p+=M; p; p /= 2) {
t[p] = max(t[p], v);
}
}
void reset(int p) {
p += M;
t[p] = pp(-inf, -1);
for(p/=2; p; p/=2) {
t[p] = max(t[p*2], t[p*2+1]);
}
}
} T;
int n, m;
const int maxn = int(5e5) + 10;
pp room[maxn];
pp req[maxn];
int main()
{
int o;
cppio(); cin >> n >> m >> o;
rrep(i, n) { cin >> room[i].x >> room[i].y; }
rrep(i, m) { cin >> req[i].y >> req[i].x; }
sort(room+1, room+n+1);
sort(req+1, req+m+1);
rrep(i, m) T.put(i, pp(req[i].y, i));
ll ans = 0;
int match = 0;
for(int i=1; match<=o && i<=n; ++i) {
int to = lower_bound(req+1, req+m+1, pp(room[i].y+1, -1)) - req;
pp m = T.rmax(1, to-1);
if(m.y == -1) continue;
int df = m.x - room[i].x;
if(df < 0) continue;
if(0) printf("For room (cost=%d, size=%d), we choose request (minsize=%d, gain=%d)\n",
room[i].x, room[i].y, req[m.y].x, req[m.y].y);
ans += df;
++match;
T.reset(m.y);
}
cout << ans << endl;
return 0;
}
Compilation message
hot.cpp: In function 'void read(int&)':
hot.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(int& x){ scanf("%d",&x); }
~~~~~^~~~~~~~~
hot.cpp: In function 'void read(ll&)':
hot.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(ll& x){ scanf("%lld",&x); }
~~~~~^~~~~~~~~~~
hot.cpp: In function 'void read(pp&)':
hot.cpp:8:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(pp& x){ scanf("%d%d",&x.first, &x.second); }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp: In function 'void read(pll&)':
hot.cpp:9:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
void read(pll& x){ scanf("%lld%lld",&x.first, &x.second); }
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
896 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
3148 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
5348 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
3576 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
14396 KB |
Output is correct |
| 2 |
Incorrect |
92 ms |
9100 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
28352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
32248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
