oj.uz

Submission #340987

# Submission time Handle Problem Language Result Execution time Memory
340987 2020-12-28T20:46:54 Z ijxjdjd Examination (JOI19_examination) C++14
0 / 100
 3000 ms 8284 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = (int)(1e5)+5;

struct query {
    int X;
    int Y;
    int Z;
    int i;
};
vector<query> vec;
vector<int> byB;
unordered_map<int, int> cnt;
int ans[MAXN];
const int K = 3005;
int arr[MAXN];
vector<int> keep[MAXN/K + 5];
int main() {
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        int A, B;
        cin >> A >> B;
        vec.push_back({A, B, -1, -1});
        byB.push_back(B);
    }
    sort(byB.begin(), byB.end());
    int c = 1;
    for (int i = 1; i < N; i++) {
        if (byB[i] != byB[i-1]) {
            cnt[byB[i-1]] = c;
        }
        c++;
    }
    cnt[byB[N-1]] = c;
    for (int i = 0; i < Q; i++) {
        int X, Y, Z;
        cin >> X >> Y >> Z;
        vec.push_back({X, Y, Z, i});
    }
    sort(vec.begin(), vec.end(), [](const query& lhs, const query& rhs) {
         if (lhs.X != rhs.X) return lhs.X > rhs.X;
        if (lhs.Y != rhs.Y) return lhs.Y > rhs.Y;
        return lhs.i < rhs.i;})
        ;
    for (query q : vec) {
        if (q.i != -1) {
            int low = 0;
            int high = N-1;
            while (low < high) {
                int mid = (low + high)/2;
                if (byB[mid] >= q.Y) {
                    high = mid;
                }
                else {
                    low = mid+1;
                }
            }
            if (byB[high] >= q.Y) {
                for (int i = N-1; i >= high;) {
                    if ((i/K)*K >= high) {
                        if (keep[i/K].size() > 0) {
                            low = 0;
                            high = keep[i/K].size()-1;
                            while (low < high) {
                                int mid = (low + high)/2;
                                if (keep[i/K][mid] >= q.Z) {
                                    high = mid;
                                }
                                else {
                                    low = mid+1;
                                }
                            }
                            if (keep[i/K][high] >= q.Z) {
                                ans[q.i] += keep[i/K].size() - high;
                            }
                        }
                        i = (i/K)*K - 1;
                    }
                    else {
                        if (arr[i] >= q.Z) {
                            ans[q.i]++;
                        }
                        i--;
                    }
                }
            }
        }
        else {
            cnt[q.Y]--;
            arr[cnt[q.Y]] = q.X + q.Y;
            keep[cnt[q.Y]/K].push_back(q.X + q.Y);
            sort(keep[cnt[q.Y]/K].begin(), keep[cnt[q.Y]/K].end());
        }
    }
    for (int i = 0; i < Q; i++) {
            cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 238 ms 748 KB Output is correct
8 Correct 236 ms 876 KB Output is correct
9 Correct 239 ms 768 KB Output is correct
10 Correct 273 ms 748 KB Output is correct
11 Correct 182 ms 876 KB Output is correct
12 Incorrect 171 ms 748 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 8284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 8284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 238 ms 748 KB Output is correct
8 Correct 236 ms 876 KB Output is correct
9 Correct 239 ms 768 KB Output is correct
10 Correct 273 ms 748 KB Output is correct
11 Correct 182 ms 876 KB Output is correct
12 Incorrect 171 ms 748 KB Output isn't correct
13 Halted 0 ms 0 KB -