Submission #1108606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108606		FubuGold	Examination (JOI19_examination)	C++14	43 / 100	1274 ms	481164 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int SQRT = 350;
const int NUM_B = MAXN / SQRT;

struct BIT {
    vector<int> tree;
    int n;
    int total_sum;
    void init(int n) {
        this->n = n;
        total_sum = 0;
        tree.assign(n+1,0);
    }
    void update(int pos,int val) {
        total_sum += val;
        for (;pos <= n;pos += pos & (-pos)) tree[pos] += val;
    }
    int query(int pos) {
        int sum = 0;
        for (;pos > 0;pos -= pos & (-pos)) sum += tree[pos];
        return sum;
    }
    int suf_query(int pos) {
        assert(pos <= n);
        return total_sum - query(pos-1);
    }
} tree[NUM_B+2];

vector<int> compress[3];
vector<vector<int>> point;
void clear_vec(vector<int> &vec) {
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
}
int get_id(int x,vector<int> &vec) {
    return lower_bound(vec.begin(),vec.end(),x) - vec.begin() + 1;
}
struct Query {
    int a,b,c,id,type;
    bool operator < (const Query &qr) {
        if (c == qr.c) return type < qr.type;
        return c > qr.c;
    }
};
vector<Query> query;
int n,q;
int ans[MAXN+1];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    for (int i=1;i<=n;i++) {
        Query qr; cin >> qr.a >> qr.b;
        qr.id = i;
        qr.type = 0;
        qr.c = qr.a + qr.b;
        compress[0].push_back(qr.a);
        compress[1].push_back(qr.b);
        compress[2].push_back(qr.c);
        query.push_back(qr);
    }
    for (int i=1;i<=q;i++) {
        Query qr; cin >> qr.a >> qr.b >> qr.c;
        qr.id = i;
        qr.type = 1;
        compress[0].push_back(qr.a);
        compress[1].push_back(qr.b);
        compress[2].push_back(qr.c);
        query.push_back(qr);
    }

    sort(query.begin(),query.end());
    for (int i=0;i<3;i++) clear_vec(compress[i]);
    int comp_a_sz = compress[0].size();
    point.assign(comp_a_sz+10,vector<int>());
    int mx_b_id = comp_a_sz / SQRT;
    for (int i=1 / SQRT;i<=mx_b_id;i++) tree[i].init(compress[1].size()+1);

    for (int qr_id = 0; qr_id < query.size();qr_id++) {
        Query qr = query[qr_id];
//        cerr << qr_id << ' ' << qr.type << ' ' << qr.id << '\n';
        qr.a = get_id(qr.a,compress[0]);
        qr.b = get_id(qr.b,compress[1]);
        qr.c = get_id(qr.c,compress[2]);
        if (qr.type == 0) {
            tree[qr.a / SQRT].update(qr.b,1);
//            assert(point[qr.a].empty() || point[qr.a].back() >= qr.b);
            point[qr.a].push_back(qr.b);
        }
        else {
            int cur_id = qr.a / SQRT;
            int cnt = 0;
            for (int i = cur_id + 1; i <= mx_b_id;i++) {
                cnt += tree[i].suf_query(qr.b);
            }
//            cerr << "ok1\n";
            for (int i = qr.a; i / SQRT == cur_id && i <= comp_a_sz;i++) {
//                cerr << i << ' ' << point.size() << ' ' << '\n';
//                cerr << ' ' << upper_bound(point[i].begin(),point[i].end(),qr.b,greater<int>()) - point[i].begin() << '\n';
                cnt += upper_bound(point[i].begin(),point[i].end(),qr.b,greater<int>()) - point[i].begin();
            }
            ans[qr.id] = cnt;
        }
    }
    for (int i=1;i<=q;i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int qr_id = 0; qr_id < query.size();qr_id++) {
      |                         ~~~~~~^~~~~~~~~~~~~~

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