oj.uz

Submission #1082808

# Submission time Handle Problem Language Result Execution time Memory
1082808 2024-09-01T16:22:31 Z DeathIsAwe Examination (JOI19_examination) C++17
20 / 100
 310 ms 23300 KB 
#include <bits/stdc++.h>
using namespace std;
int segmenta[262144], segmentb[262144];
unordered_map<int,int> compressa, compressb;


void update(int x, int pos, int *segment) {
    pos += 131072;
    while (pos > 0) {
        segment[pos] += x; pos /= 2;
    }
}


int range(int a, int b, int *segment) {
    int val = 0;
    a += 131072; b += 131072;
    while (a <= b) {
        if (a%2 == 1) {val += segment[a++];}
        if (b%2 == 0) {val += segment[b--];}
        a/=2; b/=2;
    }
    return val;
}


void compress(vector<int> &arr, unordered_map<int,int> &compress) {
    sort(arr.begin(), arr.end());
    int count = 0; compress[arr[0]] = 0;
    for (int i=1;i<arr.size();i++) {
        if (arr[i] > arr[i-1]) {
            count++;
            compress[arr[i]] = count;
        }
    }
}


bool comp(vector<int> a, vector<int> b) {
    return a[2] > b[2];
}


void querycompress(vector<vector<int>> &q, vector<int> &arra, vector<int> &arrb) {
    int pos;
    for (int i=0;i<q.size();i++) {
        pos = lower_bound(arra.begin(), arra.end(), q[i][0]) - arra.begin();
        if (pos == arra.size()) {
            q[i][0] = compressa[arra[pos-1]] + 1;
        } else {
            q[i][0] = compressa[arra[pos]];
        }
        pos = lower_bound(arrb.begin(), arrb.end(), q[i][1]) - arrb.begin();
        if (pos == arrb.size()) {
            q[i][1] = compressb[arrb[pos-1]] + 1;
        } else {
            q[i][1] = compressb[arrb[pos]];
        }
    }
}


int main() {
    int n, q; cin >> n >> q;
    vector<vector<int>> ppl(n, vector<int>(3));
    vector<int> arra(n), arrb(n), ansvec(q), query(4);
    vector<vector<int>> aq, bq;
    for (int i=0;i<n;i++) {
        cin >> ppl[i][0] >> ppl[i][1];
        ppl[i][2] = ppl[i][0] + ppl[i][1];
        arra[i] = ppl[i][0]; arrb[i] = ppl[i][1];
    }
    for (int i=0;i<q;i++) {
        cin >> query[0] >> query[1] >> query[2]; query[3] = i;
        if (query[2] <= query[0] + query[1]) {
            aq.push_back(query);
        } else {
            bq.push_back(query);
        }
    }
    compress(arra, compressa); compress(arrb, compressb);


    for (int i=0;i<n;i++) {
        ppl[i][0] = compressa[ppl[i][0]];
        ppl[i][1] = compressb[ppl[i][1]];
    }
    querycompress(aq, arra, arrb); querycompress(bq, arra, arrb);


    for (int i=0;i<262144;i++) {segmentb[i] = 0;}
    sort(ppl.begin(), ppl.end(), greater<vector<int>>());
    sort(aq.begin(), aq.end(), greater<vector<int>>());
    int tracker = 0;
    for (int i=0;i<aq.size();i++) {
        while (tracker < n && ppl[tracker][0] >= aq[i][0]) {
            update(1, ppl[tracker][1], segmentb);
            tracker++;
        }
        ansvec[aq[i][3]] = range(aq[i][1], 131071, segmentb);
    }


    for (int i=0;i<262144;i++) {segmenta[i] = 0; segmentb[i] = 0;}
    for (vector<int> i: ppl) {update(1, i[0], segmenta);}
    sort(ppl.begin(), ppl.end(), comp);
    sort(bq.begin(), bq.end(), comp);
    tracker = 0;
    for (int i=0;i<bq.size();i++) {
        while (tracker < n && ppl[tracker][2] >= bq[i][2]) {
            update(1, ppl[tracker][1], segmentb);
            update(-1, ppl[tracker][0], segmenta);
            tracker++;
        }
        ansvec[bq[i][3]] = range(bq[i][1], 131071, segmentb) - range(0, bq[i][0] - 1, segmenta);
    }
    for (int i: ansvec) {
        cout << i << '\n';
    }
}

Compilation message

examination.cpp: In function 'void compress(std::vector<int>&, std::unordered_map<int, int>&)':
examination.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=1;i<arr.size();i++) {
      |                  ~^~~~~~~~~~~
examination.cpp: In function 'void querycompress(std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
examination.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0;i<q.size();i++) {
      |                  ~^~~~~~~~~
examination.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (pos == arra.size()) {
      |             ~~~~^~~~~~~~~~~~~~
examination.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (pos == arrb.size()) {
      |             ~~~~^~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i=0;i<aq.size();i++) {
      |                  ~^~~~~~~~~~
examination.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i=0;i<bq.size();i++) {
      |                  ~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 22740 KB Output is correct
2 Correct 261 ms 22728 KB Output is correct
3 Correct 268 ms 22780 KB Output is correct
4 Correct 201 ms 19452 KB Output is correct
5 Correct 224 ms 19456 KB Output is correct
6 Correct 166 ms 15968 KB Output is correct
7 Correct 255 ms 22784 KB Output is correct
8 Correct 255 ms 22768 KB Output is correct
9 Correct 254 ms 23300 KB Output is correct
10 Correct 236 ms 19972 KB Output is correct
11 Correct 209 ms 19372 KB Output is correct
12 Correct 137 ms 15612 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 22740 KB Output is correct
2 Correct 261 ms 22728 KB Output is correct
3 Correct 268 ms 22780 KB Output is correct
4 Correct 201 ms 19452 KB Output is correct
5 Correct 224 ms 19456 KB Output is correct
6 Correct 166 ms 15968 KB Output is correct
7 Correct 255 ms 22784 KB Output is correct
8 Correct 255 ms 22768 KB Output is correct
9 Correct 254 ms 23300 KB Output is correct
10 Correct 236 ms 19972 KB Output is correct
11 Correct 209 ms 19372 KB Output is correct
12 Correct 137 ms 15612 KB Output is correct
13 Incorrect 310 ms 23224 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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