제출 #375089

#제출 시각아이디문제언어결과실행 시간메모리
375089wiwihoExamination (JOI19_examination)C++14
100 / 100
457 ms15016 KiB
#include <bits/stdc++.h>
 
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
 
using namespace std;
 
typedef long long ll;
 
vector<int> BIT;
 
int lowbit(int x){
    return x & -x;
}
 
void modify(int x, int v){
    for(; x < BIT.size(); x += lowbit(x)){
        BIT[x] += v;
    }
}
 
int query(int x){
    int ans = 0;
    for(; x > 0; x -= lowbit(x)){
        ans += BIT[x];
    }
    return ans;
}
 
vector<int> tv;
 
struct OAO{
    int x = 0, y = 0, z = 0, type = -1;
    OAO(int x = 0, int y = 0, int z = 0, int type = -1):
            x(x), y(y), z(z), type(type) {}
    void upd(){
        x = lower_bound(iter(tv), x, greater<>()) - tv.begin() + 1;
        y = lower_bound(iter(tv), y, greater<>()) - tv.begin() + 1;
        z = lower_bound(iter(tv), z, greater<>()) - tv.begin() + 1;
    }
};
 
bool comp(OAO a, OAO b){
    if(a.x == b.x) return a.type < b.type;
    return a.x < b.x;
}
 
ostream& operator<<(ostream& o, OAO oao){
    return o << '(' << oao.x << ',' << oao.y << ',' << oao.z << ',' << oao.type << ')';
}
 
vector<int> ans;
void cdq(vector<OAO>& a, int l, int r){
    if(l >= r) return;
    int m = (l + r) / 2;
    cdq(a, l, m);
    cdq(a, m + 1, r);
    //cerr << "test " << l << " " << r << "\n";
    //printv(a, cerr);
    //for(int i = 1; i < BIT.size(); i++) cerr << query(i) << " ";
    //cerr << "\n";
 
    vector<OAO> b;
    int lp = l, rp = m + 1;
    while(lp <= m && rp <= r){
        if(a[lp].y <= a[rp].y){
            if(a[lp].type == -1){
                modify(a[lp].z, 1);
            }
            b.eb(a[lp]);
            lp++;
        }
        else{
            if(a[rp].type != -1){
                ans[a[rp].type] += query(a[rp].z);
            }
            b.eb(a[rp]);
            rp++;
        }
    }
    while(lp <= m){
        if(a[lp].type == -1){
            modify(a[lp].z, 1);
        }
        b.eb(a[lp]);
        lp++;
    }
    while(rp <= r){
        if(a[rp].type != -1){
            ans[a[rp].type] += query(a[rp].z);
        }
        b.eb(a[rp]);
        rp++;
    }
 
    for(int i = l; i <= m; i++){
        if(a[i].type == -1) modify(a[i].z, -1);
    }
 
    for(int i = l; i <= r; i++) a[i] = b[i - l];
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
    ans.resize(q);
    
    vector<OAO> a;
    for(int i = 0; i < n; i++){
        int s, t;
        cin >> s >> t;
        a.eb(OAO(s, t, s + t, -1));
        tv.eb(s);
        tv.eb(t);
        tv.eb(s + t);
    }
 
    for(int i = 0; i < q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a.eb(OAO(x, y, z, i));
        tv.eb(x);
        tv.eb(y);
        tv.eb(z);
    }
 
    sort(iter(tv), greater<>());
    tv.resize(unique(iter(tv)) - tv.begin());
    BIT.resize(tv.size() + 1);
 
    for(auto& i : a){
        i.upd();
    }
    sort(iter(a), comp);
    //printv(tv, cerr);
 
    cdq(a, 0, (int)a.size() - 1);
 
    for(int i = 0; i < q; i++) cout << ans[i] << "\n";
 
    return 0;
}

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

examination.cpp: In function 'void modify(int, int)':
examination.cpp:21:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(; x < BIT.size(); x += lowbit(x)){
      |           ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...