Submission #733371

#	Time	Username	Problem	Language	Result	Execution time	Memory
733371		benjaminkleyn	Examination (JOI19_examination)	C++17	41 / 100	170 ms	15076 KiB

examination

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

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

struct Student
{
    int s, t, idx;
    Student() : 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;

    vector<Student> students(n);
    for (Student &x : students)
        cin >> x.s >> 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));
    }

    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: 0 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 0 / 57