제출 #1316974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316974		pobe	Examination (JOI19_examination)	C++20	100 / 100	1883 ms	160468 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>;
ostream &operator <<(ostream &out, vector <int> val) {
    for (auto v : val) {
        out << v  << ' ';
    }
    return out;
}
struct mst {
    int n;
    vector <int> val;
    vector <ordered_set> tree;
    void upt(int num, int l, int r, int ind) {
        tree[num].insert(val[ind]);
        if (l == r - 1) {
            return;
        }
        int med = (l + r) / 2;
        if (med > ind) {
            upt(2 * num + 1, l, med, ind);
        } else {
            upt(2 * num + 2, med, r, ind);
        }
    }
    int get(int num, int l, int r, int low, int high, int k) {
        if (l >= low && r <= high) {
            if (tree[num].empty()) {
                return 0;
            }
            return tree[num].size() - tree[num].order_of_key(k);
        }
        int med = (l + r) / 2;
        int ans = 0;
        if (med > low) {
            ans += get(2 * num + 1, l, med, low, high, k);
        }
        if (med < high) {
            ans += get(2 * num + 2, med, r, low, high, k);
        }
        return ans;
    }
public:
    void init(int nn, vector <int> &nval) {
        val = nval;
        n = nn;
        tree.resize(4 * n);
    }
    int get(int l, int r, int k) {
        if (l >= r) {
            return 0;
        }
        return get(0, 0, n, l, r, k);
    }
    void upt(int ind) {
        upt(0, 0, n, ind);
    }
};
struct query {
    int a, b, c, ind;
    void init(int num) {
         cin >> a >> b >> c;
         ind = num;
    }
};
struct value {
    int s, t, ind;
    void init(int num) {
        cin >> s >> t;
        ind = num;
    }
};

void solve() {
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector <value> val(n);
    for (int i = 0; i < n; ++i) {
        val[i].init(i);
    }
    vector <query> q(m);
    for (int i = 0; i < m; ++i) {
        q[i].init(i);
    }
    sort(q.begin(), q.end(), [](query &v1, query &v2) {
        return v1.c > v2.c;
    });
    sort(val.begin(), val.end(), [](value &v1, value &v2) {
        return v1.s < v2.s;
    });
    for (int i = 0; i < n; ++i) {
        val[i].ind = i;
    }
    auto nval = val;
    sort(nval.begin(), nval.end(), [](value &v1, value &v2) {
        return v1.s + v1.t > v2.s + v2.t;
    });
    vector <int> cv(n);
    for (int i = 0; i < n; ++i) {
        cv[i] = val[i].t;
    }
    mst now;
    now.init(n, cv);
    int ind1 = 0;
    vector <pair <int, int>> ans;
    for (int i = 0; i < m; ++i) {
        while (ind1 < n && nval[ind1].s + nval[ind1].t >= q[i].c) {
            now.upt(nval[ind1].ind);
            ++ind1;
        }
        int l = - 1, r = n;
        while (r - l > 1) {
            int med = (l + r) / 2;
            if (val[med].s < q[i].a) {
                l = med;
            } else {
                r = med;
            }
        }
        ans.emplace_back(q[i].ind, now.get(r, n, q[i].b));
    }
    sort(ans.begin(), ans.end());
    for (auto v : ans) {
        cout << v.second << '\n';
    }
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57