Submission #733375

#	Time	Username	Problem	Language	Result	Execution time	Memory
733375		benjaminkleyn	Examination (JOI19_examination)	C++17	100 / 100	653 ms	50376 KiB

examination

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Query
{
    int a, b, A, B, C, idx;
    Query() : a(0), b(0), A(0), B(0), C(0), idx(0) {}
    Query(int _a, int _b, int _c, int _idx) : a(0), b(0), A(_a), B(_b), C(_c), idx(_idx) {}
};

struct Student
{
    int s, t, S, T, idx;
    Student() : s(0), t(0), S(0), T(0), idx(0) {}
};

int n, q;

struct SegTree
{
    int t[1000000] = {0};
    SegTree() {}
    void update(int idx, int v = 1, int tl = 0, int tr = 200000)
    {
        if (tl == tr)
        {
            t[v]++;
            return;
        }
        int tm = (tl + tr) / 2;
        if (idx <= tm)
            update(idx, 2 * v, tl, tm);
        else
            update(idx, 2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
    int query(int l, int r, int v = 1, int tl = 0, int tr = 200000)
    {
        if (l > r || r < tl || tr < l)
            return 0;
        if (l <= tl && tr <= r)
            return t[v];
        int tm = (tl + tr) / 2;
        return query(l, r, 2 * v, tl, tm) + query(l, r, 2 * v + 1, tm + 1, tr);
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;

    set<int> a_vals, b_vals;

    vector<Student> students(n);
    for (Student &x : students)
    {
        cin >> x.S >> x.T;
        a_vals.insert(x.S);
        b_vals.insert(x.T);
    }

    vector<Query> type1, type2;
    for (int i = 0, a, b, c; i < q; i++)
    {
        cin >> a >> b >> c;
        if (a + b >= c)
            type1.push_back(Query(a, b, c, i));
        else
            type2.push_back(Query(a, b, c, i));

        a_vals.insert(a);
        b_vals.insert(b);
    }

    unordered_map<int, int> smolA, smolB;
    int mxA = 0;
    for (int a : a_vals)
        smolA[a] = mxA++;
    int mxB = 0;
    for (int b : b_vals)
        smolB[b] = mxB++;

    for (Student &x : students)
    {
        x.s = smolA[x.S];
        x.t = smolB[x.T];
    }
    for (Query &Q : type1)
    {
        Q.a = smolA[Q.A];
        Q.b = smolB[Q.B];
    }
    for (Query &Q : type2)
    {
        Q.a = smolA[Q.A];
        Q.b = smolB[Q.B];
    }

    vector<int> res(q);

    SegTree seg1;
    sort(type1.begin(), type1.end(), [] (const Query &X, const Query &Y) {return X.A > Y.A;});
    sort(students.begin(), students.end(), [] (const Student &X, const Student &Y) {return X.S > Y.S;});
    int i = 0;
    for (const Query &Q : type1)
    {
        while (i < n && students[i].S >= Q.A)
            seg1.update(students[i++].t);
        res[Q.idx] = seg1.query(Q.b, 200000);
    }

    seg1 = SegTree();
    SegTree seg2;
    sort(type2.begin(), type2.end(), [] (const Query &X, const Query &Y) {return X.C > Y.C;});
    sort(students.begin(), students.end(), [] (const Student &X, const Student &Y) {return X.S + X.T > Y.S + Y.T;});
    i = 0;
    for (const Query &Q : type2)
    {
        while (i < n && students[i].S + students[i].T >= Q.C)
        {
            seg1.update(students[i].s);
            seg2.update(students[i].t);
            i++;
        }
        res[Q.idx] = seg1.query(Q.a, 200000) - seg2.query(0, Q.b - 1);
    }

    for (int j = 0; j < q; j++)
        cout << res[j] << '\n';

    return 0;
}

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