Submission #216332

#	Time	Username	Problem	Language	Result	Execution time	Memory
216332		DystoriaX	Examination (JOI19_examination)	C++14	100 / 100	833 ms	42212 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200010;

struct BIT{
    vector<int> bit;

    int query(int x){
        int ret = 0;

        for(; x; x -= x & (-x)) ret += bit[x];

        return ret;
    }

    void update(int x, int val){
        for(; x < MAX; x += x & (-x)) bit[x] += val;
    }

    BIT(){
        bit.assign(MAX, 0);
    }

    void init(){
        bit.assign(MAX, 0);
    }
} bitX, bitY;

struct Query{
    int x, y, z, idx;
    bool spec = false;
};

int n, q;
map<int, int> c[3];
vector<int> cp[3];
vector<Query> pt, qr;
int ans[MAX];

void Compress(){
    for(int i = 0; i < 3; i++){
        sort(cp[i].begin(), cp[i].end());
        cp[i].erase(unique(cp[i].begin(), cp[i].end()), cp[i].end());

        int j = 1;
        for(auto k : cp[i]) c[i][k] = j++;
    }

    for(auto &k : pt){
        k.x = c[0][k.x];
        k.y = c[1][k.y];
        k.z = c[2][k.z];
    }

    for(auto &k : qr){
        k.x = c[0][k.x];
        k.y = c[1][k.y];
        k.z = c[2][k.z];
    }
}

bool compQ(Query a, Query b){
    return a.z > b.z;
}

bool compQx(Query a, Query b){
    return a.x > b.x;
}

int main(){
    scanf("%d%d", &n, &q);

    pt.resize(n), qr.resize(q);

    for(int i = 0; i < n; i++){
        scanf("%d%d", &pt[i].x, &pt[i].y);
        pt[i].z = pt[i].x + pt[i].y;

        cp[0].emplace_back(pt[i].x);
        cp[1].emplace_back(pt[i].y);
        cp[2].emplace_back(pt[i].z);
    }

    for(int i = 0; i < q; i++){
        scanf("%d%d%d", &qr[i].x, &qr[i].y, &qr[i].z);
        
        cp[0].emplace_back(qr[i].x);
        cp[1].emplace_back(qr[i].y);
        cp[2].emplace_back(qr[i].z);

        qr[i].idx = i;
        qr[i].spec = (qr[i].x + qr[i].y < qr[i].z);
    }

    Compress();

    sort(pt.begin(), pt.end(), compQ);
    sort(qr.begin(), qr.end(), compQ);

    int id = 0;
    for(auto &k : qr){
        // cout << "Processing " << k.idx << endl;

        while(id < n && pt[id].z >= k.z){
            bitX.update(pt[id].x, 1);
            bitY.update(pt[id].y, 1);
            id++;

            // cout << "Added " << pt[id - 1].x << " " << pt[id - 1].y << endl;
        }

        //Derived from validX + validY - totalValid
        if(k.spec) ans[k.idx] = id - bitX.query(k.x - 1) - bitY.query(k.y - 1);
    }

    sort(pt.begin(), pt.end(), compQx);
    sort(qr.begin(), qr.end(), compQx);

    bitY.init();

    id = 0;
    for(auto &k : qr){
        if(k.spec) continue;

        while(id < n && pt[id].x >= k.x){
            bitY.update(pt[id].y, 1);
            id++;
        }

        ans[k.idx] = id - bitY.query(k.y - 1);
    }

    for(int i = 0; i < q; i++) printf("%d\n", ans[i]);
    
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &pt[i].x, &pt[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &qr[i].x, &qr[i].y, &qr[i].z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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