Submission #157177

#	Time	Username	Problem	Language	Result	Execution time	Memory
157177		EntityIT	Examination (JOI19_examination)	C++14	100 / 100	538 ms	26180 KiB

examination

#include<bits/stdc++.h>

using namespace std;

const int NStu = (int)1e5 + 5, NQue = NStu;

int nStu, nQue, ans[NQue];
vector<int> compMath, compInfo;

struct Stu {
    int math, info;
    Stu(int _math = 0, int _info = 0) : math(_math), info(_info) {}
    bool operator<(const Stu &_) const { return math + info < _.math + _.info; }
} stu[NStu];

struct Que {
    int a, b, c, initId;
    Que(int _a = 0, int _b = 0, int _c = 0, int _initId = 0) : a(_a), b(_b), c(_c), initId(_initId) {}
    bool operator<(const Que &_) const { return c < _.c; }
} que[NQue];

struct Bit2D {
    vector<int> infoCnt[NStu];
    vector<int> compInfo[NStu];
    void updCompInfo(int math, int info) {
        int x = (int)(lower_bound(compMath.begin(), compMath.end(), math) - compMath.begin() ) + 1;
        for (; x < NStu; x += x & -x) {
            compInfo[x].emplace_back(info);
        }
    }
    void prep() {
        for (int i = 1; i < NStu; ++i) {
            sort(compInfo[i].begin(), compInfo[i].end() );
            compInfo[i].erase(unique(compInfo[i].begin(), compInfo[i].end() ), compInfo[i].end() );
            infoCnt[i].assign( (int)compInfo[i].size() + 1, 0);
        }
    }
    void upd(int math, int info, int val) {
        int x = (int)(lower_bound(compMath.begin(), compMath.end(), math) - compMath.begin() ) + 1;
        for (; x < NStu; x += x & -x) {
            int y = (int)(lower_bound(compInfo[x].begin() , compInfo[x].end(), info) - compInfo[x].begin() ) + 1;
            for (; y < (int)infoCnt[x].size(); y += y & -y) infoCnt[x][y] += val;
        }
    }
    int get(int math, int info) {
        int ret = 0,
            x = (int)(upper_bound(compMath.begin(), compMath.end(), math) - compMath.begin() );
        for (; x > 0; x -= x & -x) {
            int y = (int)(upper_bound(compInfo[x].begin() , compInfo[x].end(), info) - compInfo[x].begin() );
            for (; y > 0; y -= y & -y) ret += infoCnt[x][y];
        }
        return ret;
    }
} bit2D;

int main() {
//    freopen("input", "r", stdin);

    scanf(" %d %d", &nStu, &nQue);

    for (int i = 1; i <= nStu; ++i) {
        scanf(" %d %d", &stu[i].math, &stu[i].info);
        stu[i].math = -stu[i].math; compMath.emplace_back(stu[i].math);
        stu[i].info = -stu[i].info;
    }
    sort(stu + 1, stu + nStu + 1);

    for (int i = 1; i <= nQue; ++i) {
        scanf(" %d %d %d", &que[i].a, &que[i].b, &que[i].c);
        que[i].a = -que[i].a;
        que[i].b = -que[i].b;
        que[i].c = -que[i].c;
        que[i].initId = i;
    }
    sort(que + 1, que + nQue + 1);

    sort(compMath.begin(), compMath.end() );
    compMath.erase(unique(compMath.begin(), compMath.end() ), compMath.end() );

    for (int i = 1; i <= nStu; ++i) {
        bit2D.updCompInfo(stu[i].math, stu[i].info);
    }
    bit2D.prep();

    int iStu = 1;
    for (int i = 1; i <= nQue; ++i) {
        while (iStu <= nStu && stu[iStu].math + stu[iStu].info <= que[i].c) {
            bit2D.upd(stu[iStu].math, stu[iStu].info, 1);
            ++iStu;
        }
        ans[ que[i].initId ] = bit2D.get(que[i].a, que[i].b);
    }

    for (int i = 1; i <= nQue; ++i) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d", &nStu, &nQue);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d", &stu[i].math, &stu[i].info);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d %d", &que[i].a, &que[i].b, &que[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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