Submission #1010325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010325		MohamedFaresNebili	Examination (JOI19_examination)	C++14	0 / 100	136 ms	27596 KiB

examination

#include <bits/stdc++.h>

        using namespace std;

        int N, Q;
        int S[100005], T[100005];
        vector<int> A[100005];
        vector<int> st[400005];

        void build(int v, int l, int r) {
            if(l == r) {
                for(auto u : A[l])
                    st[v].push_back(u);
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            int i = 0, j = 0;
            int A = st[v * 2].size();
            int B = st[v * 2 + 1].size();
            while(i < A || j < B) {
                if(i == A) st[v].push_back(st[v * 2 + 1][j++]);
                else if(j == B) st[v].push_back(st[v * 2][i++]);
                else if(st[v * 2][i] < st[v * 2 + 1][j])
                    st[v].push_back(st[v * 2][i++]);
                else st[v].push_back(st[v * 2 + 1][j++]);
            }
        }

        int query(int v, int l, int r, int lo, int hi, int p) {
            if(l > hi || r < lo) return 0;
            if(l >= lo && r <= hi)
                return st[v].size() - (lower_bound(st[v].begin(), st[v].end(), p) - st[v].begin());
            return query(v * 2, l, (l + r) / 2, lo, hi, p)
                + query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, p);
        }

        int32_t main() {
            ios_base::sync_with_stdio(0);
            cin.tie(0); cout.tie(0);
            cin >> N >> Q;
            for(int l = 0; l < N; l++) {
                cin >> S[l] >> T[l];
                A[S[l]].push_back(T[l]);
            }
            for(int l = 0; l < 100005; l++)
                sort(A[l].begin(), A[l].end());
            build(1, 1, 100000);
            while(Q--) {
                int X, Y, Z; cin >> X >> Y >> Z;
                cout << query(1, 1, 100000, X, 100000, Y) << "\n";
            }
            return 0;
        }

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