oj.uz

Submission #340992

# Submission time Handle Problem Language Result Execution time Memory
340992 2020-12-28T20:54:12 Z ijxjdjd Examination (JOI19_examination) C++14
2 / 100
 3000 ms 8668 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++) {
        arr[i] = -1;
        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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 244 ms 748 KB Output is correct
8 Correct 247 ms 748 KB Output is correct
9 Correct 251 ms 620 KB Output is correct
10 Correct 286 ms 620 KB Output is correct
11 Correct 185 ms 712 KB Output is correct
12 Correct 171 ms 620 KB Output is correct
13 Correct 245 ms 748 KB Output is correct
14 Correct 244 ms 748 KB Output is correct
15 Correct 245 ms 836 KB Output is correct
16 Correct 290 ms 768 KB Output is correct
17 Correct 282 ms 748 KB Output is correct
18 Correct 41 ms 620 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 8668 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 3055 ms 8668 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 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 244 ms 748 KB Output is correct
8 Correct 247 ms 748 KB Output is correct
9 Correct 251 ms 620 KB Output is correct
10 Correct 286 ms 620 KB Output is correct
11 Correct 185 ms 712 KB Output is correct
12 Correct 171 ms 620 KB Output is correct
13 Correct 245 ms 748 KB Output is correct
14 Correct 244 ms 748 KB Output is correct
15 Correct 245 ms 836 KB Output is correct
16 Correct 290 ms 768 KB Output is correct
17 Correct 282 ms 748 KB Output is correct
18 Correct 41 ms 620 KB Output is correct
19 Execution timed out 3055 ms 8668 KB Time limit exceeded
20 Halted 0 ms 0 KB -