Submission #293127

#	Time	Username	Problem	Language	Result	Execution time	Memory
293127		BeanZ	Exhibition (JOI19_ho_t2)	C++14	0 / 100	1 ms	384 KiB

joi2019_ho_t2

#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) return 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 res = {0, 0};
                //cout << a[i].first << " " << a[i].second << endl;
                for (int j = 1; j <= a[i].second; j++){
                        viet x = get(1, 1, val.size(), j, j);
                        //cout << i << ": " << x.mx << " " << x.id << endl;
                        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){
                                res = min(res, {x.mx + 1, l});
                        }
                }
                upd(1, 1, val.size(), a[i].second, res);
                ans = max(ans, res.mx);
        }
        cout << ans;
}
/*
5 5
1 10
2 1
3 5
4 1
5 90
2
3
5
6
7
*/

Compilation message (stderr)

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);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50