oj.uz

답안 #1082802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082802 2024-09-01T16:02:31 Z DeathIsAwe Examination (JOI19_examination) C++17
20 / 100
 225 ms 22036 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;
        }
    }
}


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]];
        //cout << ppl[i][0] << ' ' << ppl[i][1] << '\n';
    }
    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>>());
    //for (int i=0;i<aq.size();i++) {
    //    cout << aq[i][0] << ' ' << aq[i][1] << ' ' << aq[i][2] << ' ' << aq[i][3] << '\n';
    //}
    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: 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:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i=0;i<q.size();i++) {
      |                  ~^~~~~~~~~
examination.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (pos == arra.size()) {
      |             ~~~~^~~~~~~~~~~~~~
examination.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (pos == arrb.size()) {
      |             ~~~~^~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i=0;i<aq.size();i++) {
      |                  ~^~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 21760 KB Output is correct
2 Correct 195 ms 21760 KB Output is correct
3 Correct 201 ms 21724 KB Output is correct
4 Correct 152 ms 18492 KB Output is correct
5 Correct 165 ms 18396 KB Output is correct
6 Correct 113 ms 15108 KB Output is correct
7 Correct 186 ms 21760 KB Output is correct
8 Correct 175 ms 21756 KB Output is correct
9 Correct 198 ms 21760 KB Output is correct
10 Correct 160 ms 18256 KB Output is correct
11 Correct 148 ms 18176 KB Output is correct
12 Correct 93 ms 14688 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 21760 KB Output is correct
2 Correct 195 ms 21760 KB Output is correct
3 Correct 201 ms 21724 KB Output is correct
4 Correct 152 ms 18492 KB Output is correct
5 Correct 165 ms 18396 KB Output is correct
6 Correct 113 ms 15108 KB Output is correct
7 Correct 186 ms 21760 KB Output is correct
8 Correct 175 ms 21756 KB Output is correct
9 Correct 198 ms 21760 KB Output is correct
10 Correct 160 ms 18256 KB Output is correct
11 Correct 148 ms 18176 KB Output is correct
12 Correct 93 ms 14688 KB Output is correct
13 Incorrect 181 ms 22036 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -