oj.uz

Submission #1010319

# Submission time Handle Problem Language Result Execution time Memory
1010319 2024-06-28T17:51:43 Z MohamedFaresNebili Examination (JOI19_examination) C++14
0 / 100
 147 ms 29968 KB 
#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) {
                st[v] = A[l];
                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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 29900 KB Output is correct
2 Correct 137 ms 29968 KB Output is correct
3 Incorrect 133 ms 29900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 29900 KB Output is correct
2 Correct 137 ms 29968 KB Output is correct
3 Incorrect 133 ms 29900 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -