제출 #518546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518546		pokmui9909	Examination (JOI19_examination)	C++17	100 / 100	422 ms	36336 KiB

examination

#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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57