Submission #733377

#	Time	Username	Problem	Language	Result	Execution time	Memory
733377		benjaminkleyn	Examination (JOI19_examination)	C++17	100 / 100	572 ms	44952 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 BIT
{
    int bit[300000] = {0};
    BIT() {}
    void update(int idx)
    {
        for (; idx < 300000; idx |= (idx + 1))
            bit[idx]++;
    }
    int sum(int idx)
    {
        int res = 0;
        for (; idx >= 0; idx = (idx & (idx + 1)) - 1)
            res += bit[idx];
        return res;
    }
    int sum(int l, int r)
    {
        return sum(r) - sum(l-1);
    }
};

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

    BIT bit1;
    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)
            bit1.update(students[i++].t);
        res[Q.idx] = bit1.sum(Q.b, 200000);
    }

    bit1 = BIT();
    BIT bit2;
    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)
        {
            bit1.update(students[i].s);
            bit2.update(students[i].t);
            i++;
        }
        res[Q.idx] = bit1.sum(Q.a, 200000) - bit2.sum(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