제출 #375077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375077		wiwiho	Examination (JOI19_examination)	C++14	2 / 100	3062 ms	11372 KiB

examination

#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 == -1;
    return a.x < b.x;
}

ostream& operator<<(ostream& o, OAO oao){
    return o << '(' << oao.x << ',' << oao.y << ',' << oao.z << ',' << oao.type << ')';
}

vector<int> ans;
vector<OAO> b, a;
vector<int> cnt;
void cdq(int l, int r){
    if(l >= r) return;
    int m = (l + r) / 2;
    cdq(l, m);
    cdq(m + 1, r);
    //cerr << "test " << l << " " << r << "\n";
    //printv(a, cerr);
    //for(int i = 1; i < BIT.size(); i++) cerr << query(i) << " ";
    //cerr << "\n";

    int lp = l, rp = m + 1;
    int bp = l;
    while(lp <= m && rp <= r){
        if(a[lp].y <= a[rp].y){
            if(a[lp].type == -1){
                modify(a[lp].z, 1);
            }
            b[bp] = a[lp];
            lp++;
        }
        else{
            if(a[rp].type != -1){
                ans[a[rp].type] += query(a[rp].z);
            }
            b[bp] = a[rp];
            rp++;
        }
        bp++;
    }
    while(lp <= m){
        if(a[lp].type == -1){
            modify(a[lp].z, 1);
        }
        b[bp] = a[lp];
        lp++;
        bp++;
    }
    while(rp <= r){
        if(a[rp].type != -1){
            ans[a[rp].type] += query(a[rp].z);
        }
        b[bp] = a[rp];
        rp++;
        bp++;
    }

    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];
        cnt[i]++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    ans.resize(q);
    a.resize(n + q);
    tv.resize(3 * (n + q));
    
    for(int i = 0; i < n; i++){
        int s, t;
        cin >> s >> t;
        a[i] = OAO(s, t, s + t, -1);
        tv[i * 3] = s;
        tv[i * 3 + 1] = t;
        tv[i * 3 + 2] = s + t;
    }

    for(int i = 0; i < q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[n + i] = OAO(x, y, z, i);
        tv[(n + i) * 3] = x;
        tv[(n + i) * 3 + 1] = y;
        tv[(n + i) * 3 + 2] = z;
    }

    sort(iter(tv), greater<>());
    tv.resize(unique(iter(tv)) - tv.begin());
    BIT.resize(tv.size() + 1);
    b.resize(a.size());
    cnt.resize(a.size());

    for(auto& i : a){
        i.upd();
    }
    sort(iter(a), comp);
    //printv(tv, cerr);

    cdq(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)){
      |           ~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57