Submission #255096

#	Time	Username	Problem	Language	Result	Execution time	Memory
255096		arujbansal	Examination (JOI19_examination)	C++17	2 / 100	3090 ms	27896 KiB

examination

#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define FILE_IO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define trav(e, x) for (auto &e : x)
#define pb(x) push_back(x)
#define eb(x...) emplace_back(x)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define lc(i) 2*i+1
#define rc(i) 2*i+2
#define int long long
using namespace std;
typedef pair<int, int> ii;

struct pupil {
    pair<int, int> math, info, total;
    int dep;
};

bool comp(pupil x, pupil y) {
    if (x.total.first != y.total.first) return x.total.first < y.total.first;
    if (x.math.first != y.math.first) return x.math.first < y.math.first;
    return x.info.first < y.info.first;
}

struct SegmentTree {
    int n;
    vector<pupil> tree;


    void init(int x) {
        n = x;
        tree.resize(4 * n);
    }

    static pupil merge(pupil x, pupil y) {
        pupil ans;
        ans.math.first = min(x.math.first, y.math.first);
        ans.math.second = max(x.math.second, y.math.second);

        ans.info.first = min(x.info.first, y.info.first);
        ans.info.second = max(x.info.second, y.info.second);

        ans.total.first = min(x.total.first, y.total.first);
        ans.total.second = max(x.total.second, y.total.second);

        ans.dep = x.dep + y.dep;

        return ans;
    }

    void build(int i, int l, int r, vector<pupil> &a) {
        if (l == r) tree[i] = a[l];
        else {
            int mid = (l + r) / 2;
            build(lc(i), l, mid, a);
            build(rc(i), mid + 1, r, a);
            tree[i] = merge(tree[lc(i)], tree[rc(i)]);
        }
    }

    int query(int i, int l, int r, int math, int info, int total) {
        //cout << i << "\n";
        if (tree[i].math.second < math || tree[i].info.second < info || tree[i].total.second < total) return 0;
        if (tree[i].math.first >= math && tree[i].info.first >= info && tree[i].total.first >= total)
            return tree[i].dep;
        int mid = (l + r) / 2;
        return query(lc(i), l, mid, math, info, total) + query(rc(i), mid + 1, r, math, info, total);

    }

    void build(vector<pupil> &a) { build(0, 0, n - 1, a); }

    int query(int math, int info, int total) { return query(0, 0, n - 1, math, info, total); }
};


signed main() {
    FAST_IO;
    //FILE_IO;

    int n, q;
    cin >> n >> q;
    vector<pupil> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i].math.first >> students[i].info.first;
        students[i].math.second = students[i].math.first;
        students[i].info.second = students[i].info.first;
        students[i].total.first = students[i].total.second = students[i].math.first + students[i].info.first;
        students[i].dep = 1;
    }
    sort(all(students), comp);
    SegmentTree tree;
    tree.init(n);
    tree.build(students);
    //cout << tree.tree[0].math.second << " " << tree.tree[0].info.second << " " << tree.tree[0].total.second << " ";
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        cout << tree.query(x, y, z) << "\n";
    }
}

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