oj.uz

Submission #341011

# Submission time Handle Problem Language Result Execution time Memory
341011 2020-12-28T22:00:24 Z ijxjdjd Examination (JOI19_examination) C++14
0 / 100
 7 ms 5376 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 = 5;
int arr[MAXN];
vector<int> keep[MAXN];
int main() {
    string s = "input.in";
    freopen(s.c_str(), "r", stdin);
    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) {
                            int l = 0;
                            int h = keep[i/K].size()-1;
                            while (l < h) {
                                int mid = (l + h)/2;
                                if (keep[i/K][mid] >= q.Z) {
                                    h = mid;
                                }
                                else {
                                    l = mid+1;
                                }
                            }
                            if (keep[i/K][h] >= q.Z) {
                                ans[q.i] += keep[i/K].size() - h;
                            }
                        }

                        i = (i/K)*K - 1;
                    }
                    else {
                        if (arr[i] >= q.Z) {
                            ans[q.i]++;
                        }
                        i--;
                    }
                }
            }
        }
        else {
            cnt[q.Y]--;
            int a = cnt[q.Y];
            arr[a] = q.X + q.Y;
            keep[a/K].push_back(q.X + q.Y);
            sort(keep[a/K].begin(), keep[a/K].end());
        }
    }
    for (int i = 0; i < Q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     freopen(s.c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -