| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 293087 |
2020-09-07T16:06:12 Z |
BeanZ |
Exhibition (JOI19_ho_t2) |
C++14 |
|
1 ms |
384 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
struct viet{
ll mx = 0, id = 0;
bool operator <(const viet &o) const{
if (mx == o.mx) id < o.id;
return mx > o.mx;
}
};
viet st[N * 4];
pair<ll, ll> a[N];
ll b[N];
void upd(ll k, ll l, ll r, ll x, viet v){
if (x > r || x < l) return;
if (l == r){
st[k] = min(st[k], v);
return;
}
ll mid = (l + r) >> 1;
upd(k << 1, l, mid, x, v);
upd(k << 1 | 1, mid + 1, r, x, v);
st[k] = min(st[k << 1], st[k << 1 | 1]);
}
viet get(ll k, ll l, ll r, ll x, ll y){
if (x > r || y < l) return {0, 0};
if (x <= l && y >= r) return st[k];
ll mid = (l + r) >> 1;
return min(get(k << 1, l, mid, x, y), get(k << 1 | 1, mid + 1, r, x, y));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("balance.in", "r")){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
}
ll n, m;
cin >> n >> m;
vector<ll> val;
for (int i = 1; i <= n; i++){
ll s, v;
cin >> s >> v;
a[i] = {s, v};
val.push_back(v);
}
sort(a + 1, a + n + 1);
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
for (int i = 1; i <= n; i++){
a[i].second = (lower_bound(val.begin(), val.end(), a[i].second) - val.begin()) + 1;
}
ll ans = 0;
for (int i = 1; i <= m; i++) cin >> b[i];
sort(b + 1, b + m + 1);
for (int i = 1; i <= n; i++){
viet x = get(1, 1, n, 1, a[i].second);
ll l = x.id + 1, h = m;
while (l <= h){
ll mid = (l + h) >> 1;
if (a[i].first <= b[mid]) h = mid - 1;
else l = mid + 1;
}
if (l <= m){
viet res = {x.mx + 1, l};
upd(1, 1, n, a[i].second, res);
ans = max(ans, x.mx + 1);
}
}
cout << ans;
}
/*
*/
Compilation message
joi2019_ho_t2.cpp: In member function 'bool viet::operator<(const viet&) const':
joi2019_ho_t2.cpp:11:36: warning: statement has no effect [-Wunused-value]
11 | if (mx == o.mx) id < o.id;
| ~~~^~~~~~
joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:39:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
39 | freopen("balance.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t2.cpp:40:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
40 | freopen("balance.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
