oj.uz

Submission #293127

# Submission time Handle Problem Language Result Execution time Memory
293127 2020-09-07T16:39:51 Z BeanZ Exhibition (JOI19_ho_t2) C++14
0 / 100
 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) 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -