oj.uz

Submission #518546

# Submission time Handle Problem Language Result Execution time Memory
518546 2022-01-24T04:24:55 Z pokmui9909 Examination (JOI19_examination) C++17
100 / 100
 422 ms 36336 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll N, Q;
struct Qry{
    ll x, y, z, t, n;
};
Qry A[200010];
ll ans[200010];
struct BinaryIndexedTree{
    ll T[200010];
    void update(ll k, ll v){for(;k <= 200005; k += k & -k)T[k] += v;}
    ll sum(ll k){ll r = 0;for(;k;k -= k & -k) r += T[k]; return r;}
    ll query(ll l, ll r){return sum(r) - sum(l - 1);}
};
BinaryIndexedTree T;
 
void dnc(ll L, ll R){
    if(L >= R) return;
    ll m = (L + R) / 2;
    vector<Qry> V;
    for(int i = L; i <= R; i++){
        if(i <= m && A[i].t == 1) V.push_back(A[i]);
        else if(i > m && A[i].t == 0) V.push_back(A[i]);
    }
    sort(V.begin(), V.end(), [&](Qry a, Qry b) -> bool{
        if(a.x != b.x) return a.x > b.x;
        if(a.y != b.y) return a.y > b.y;
        return a.t < b.t;
    });
    for(int i = 0; i < V.size(); i++){
        if(V[i].t == 0){
            T.update(V[i].y, 1);
        } else {
            ans[V[i].n] += T.query(V[i].y, 200005);
        }
    }
    for(int i = 0; i < V.size(); i++){
        if(V[i].t == 0){
            T.update(V[i].y, -1);
        }
    }
    dnc(L, m);
    dnc(m + 1, R);
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    cin >> N >> Q;
    vector<ll> C1, C2, C3;
    for(int i = 1; i <= N; i++){
        cin >> A[i].x >> A[i].y;
        A[i].z = A[i].x + A[i].y;
        C1.push_back(A[i].x);
        C2.push_back(A[i].y);
        C3.push_back(A[i].z);
    }
    for(int i = N + 1; i <= N + Q; i++){
        cin >> A[i].x >> A[i].y >> A[i].z;
        C1.push_back(A[i].x);
        C2.push_back(A[i].y);
        C3.push_back(A[i].z);
        A[i].t = 1, A[i].n = i - N;
    }
    sort(C1.begin(), C1.end());
    sort(C2.begin(), C2.end());
    sort(C3.begin(), C3.end());
    C1.erase(unique(C1.begin(), C1.end()), C1.end());
    C2.erase(unique(C2.begin(), C2.end()), C2.end());
    C3.erase(unique(C3.begin(), C3.end()), C3.end());
    for(int i = 1; i <= N + Q; i++){
        A[i].x = lower_bound(C1.begin(), C1.end(), A[i].x) - C1.begin() + 1;
        A[i].y = lower_bound(C2.begin(), C2.end(), A[i].y) - C2.begin() + 1;
        A[i].z = lower_bound(C3.begin(), C3.end(), A[i].z) - C3.begin() + 1;
    }
    sort(A + 1, A + N + Q + 1, [&](Qry a, Qry b) -> bool{
         if(a.z == b.z) return a.t > b.t;
         return a.z < b.z;
    });
    dnc(1, N + Q);
    for(int i = 1; i <= Q; i++){
        cout << ans[i] << '\n';
    }
}

Compilation message

examination.cpp: In function 'void dnc(ll, ll)':
examination.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~
examination.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < V.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 9 ms 1240 KB Output is correct
8 Correct 9 ms 1212 KB Output is correct
9 Correct 9 ms 1232 KB Output is correct
10 Correct 8 ms 1172 KB Output is correct
11 Correct 9 ms 1232 KB Output is correct
12 Correct 7 ms 1148 KB Output is correct
13 Correct 9 ms 1356 KB Output is correct
14 Correct 8 ms 1360 KB Output is correct
15 Correct 8 ms 1360 KB Output is correct
16 Correct 7 ms 1324 KB Output is correct
17 Correct 8 ms 1112 KB Output is correct
18 Correct 5 ms 1108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 29164 KB Output is correct
2 Correct 352 ms 29160 KB Output is correct
3 Correct 346 ms 29168 KB Output is correct
4 Correct 335 ms 27784 KB Output is correct
5 Correct 319 ms 28468 KB Output is correct
6 Correct 262 ms 27004 KB Output is correct
7 Correct 358 ms 29060 KB Output is correct
8 Correct 344 ms 28972 KB Output is correct
9 Correct 346 ms 28860 KB Output is correct
10 Correct 298 ms 28416 KB Output is correct
11 Correct 300 ms 27736 KB Output is correct
12 Correct 215 ms 26912 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 29164 KB Output is correct
2 Correct 352 ms 29160 KB Output is correct
3 Correct 346 ms 29168 KB Output is correct
4 Correct 335 ms 27784 KB Output is correct
5 Correct 319 ms 28468 KB Output is correct
6 Correct 262 ms 27004 KB Output is correct
7 Correct 358 ms 29060 KB Output is correct
8 Correct 344 ms 28972 KB Output is correct
9 Correct 346 ms 28860 KB Output is correct
10 Correct 298 ms 28416 KB Output is correct
11 Correct 300 ms 27736 KB Output is correct
12 Correct 215 ms 26912 KB Output is correct
13 Correct 395 ms 27588 KB Output is correct
14 Correct 401 ms 33372 KB Output is correct
15 Correct 363 ms 29336 KB Output is correct
16 Correct 337 ms 26108 KB Output is correct
17 Correct 375 ms 26932 KB Output is correct
18 Correct 267 ms 28520 KB Output is correct
19 Correct 382 ms 27572 KB Output is correct
20 Correct 397 ms 28860 KB Output is correct
21 Correct 387 ms 27492 KB Output is correct
22 Correct 282 ms 28396 KB Output is correct
23 Correct 305 ms 27716 KB Output is correct
24 Correct 216 ms 26956 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 9 ms 1240 KB Output is correct
8 Correct 9 ms 1212 KB Output is correct
9 Correct 9 ms 1232 KB Output is correct
10 Correct 8 ms 1172 KB Output is correct
11 Correct 9 ms 1232 KB Output is correct
12 Correct 7 ms 1148 KB Output is correct
13 Correct 9 ms 1356 KB Output is correct
14 Correct 8 ms 1360 KB Output is correct
15 Correct 8 ms 1360 KB Output is correct
16 Correct 7 ms 1324 KB Output is correct
17 Correct 8 ms 1112 KB Output is correct
18 Correct 5 ms 1108 KB Output is correct
19 Correct 363 ms 29164 KB Output is correct
20 Correct 352 ms 29160 KB Output is correct
21 Correct 346 ms 29168 KB Output is correct
22 Correct 335 ms 27784 KB Output is correct
23 Correct 319 ms 28468 KB Output is correct
24 Correct 262 ms 27004 KB Output is correct
25 Correct 358 ms 29060 KB Output is correct
26 Correct 344 ms 28972 KB Output is correct
27 Correct 346 ms 28860 KB Output is correct
28 Correct 298 ms 28416 KB Output is correct
29 Correct 300 ms 27736 KB Output is correct
30 Correct 215 ms 26912 KB Output is correct
31 Correct 395 ms 27588 KB Output is correct
32 Correct 401 ms 33372 KB Output is correct
33 Correct 363 ms 29336 KB Output is correct
34 Correct 337 ms 26108 KB Output is correct
35 Correct 375 ms 26932 KB Output is correct
36 Correct 267 ms 28520 KB Output is correct
37 Correct 382 ms 27572 KB Output is correct
38 Correct 397 ms 28860 KB Output is correct
39 Correct 387 ms 27492 KB Output is correct
40 Correct 282 ms 28396 KB Output is correct
41 Correct 305 ms 27716 KB Output is correct
42 Correct 216 ms 26956 KB Output is correct
43 Correct 410 ms 30492 KB Output is correct
44 Correct 408 ms 30512 KB Output is correct
45 Correct 422 ms 36336 KB Output is correct
46 Correct 355 ms 27380 KB Output is correct
47 Correct 375 ms 28888 KB Output is correct
48 Correct 261 ms 22048 KB Output is correct
49 Correct 406 ms 36100 KB Output is correct
50 Correct 397 ms 30348 KB Output is correct
51 Correct 408 ms 33684 KB Output is correct
52 Correct 337 ms 28900 KB Output is correct
53 Correct 291 ms 28488 KB Output is correct