Submission #956260

#	Time	Username	Problem	Language	Result	Execution time	Memory
956260		_callmelucian	Examination (JOI19_examination)	C++14	100 / 100	351 ms	12280 KiB

examination

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int srt = 316;

struct strct {
    vector<int> vec, sum;
    strct (int sz) : vec(sz + 1), sum(sz / srt + 1) {}

    void update (int pos, int val) {
        vec[pos] += val;
        sum[pos / srt] += val;
    }

    int query (int k) {
        int nxt = k / srt + 1, ans = 0;
        for (int i = k; i < srt * nxt; i++) ans += vec[i];
        for (int i = nxt; i < sum.size(); i++) ans += sum[i];
        return ans;
    }
} helper(mn);

struct qry {
    int x, y, z, id;

    qry() : x(0), y(0), z(0), id(0) {}
    qry (int a, int b, int c, int d) : x(a), y(b), z(c), id(d) {}

    bool operator < (const qry &o) const {
        if (x / srt == o.x / srt) {
            if ((x / srt) & 1) return y < o.y;
            return y > o.y;
        }
        return x / srt < o.x / srt;
    }
};

int VMO[mn], VOI[mn], ans[mn], idBoth[mn], crit[mn];
vector<pii> math, info, both;

void add (int i) {
    //cout << "add student " << i << " " << crit[i] << "\n";
    if (++crit[i] == 2) helper.update(idBoth[i], 1);
}

void rem (int i) {
    //cout << "remove student " << i << " " << crit[i] << "\n";
    if (crit[i]-- == 2) helper.update(idBoth[i], -1);
}

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

    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> VMO[i] >> VOI[i];

    math = info = both = vector<pii>(n);
    for (int i = 0; i < n; i++) {
        math[i] = {VMO[i], i};
        info[i] = {VOI[i], i};
        both[i] = {VMO[i] + VOI[i], i};
    }
    sort(all(math));
    sort(all(info));
    sort(all(both));

    for (int i = 0; i < n; i++)
        idBoth[i] = lower_bound(all(both), make_pair(VMO[i] + VOI[i], i)) - both.begin();

    vector<qry> query;
    for (int i = 0; i < q; i++) {
        int a, b, c; cin >> a >> b >> c;
        int x = lower_bound(all(math), make_pair(a, 0)) - math.begin();
        int y = lower_bound(all(info), make_pair(b, 0)) - info.begin();
        int z = lower_bound(all(both), make_pair(c, 0)) - both.begin();
        if (x < n && y < n && z < n)
            query.push_back(qry(x, y, z, i));
    }
    sort(all(query));

    int iterM = n, iterI = n;
    for (qry cur : query) {
        while (iterM > cur.x) add(math[--iterM].second);
        while (iterM < cur.x) rem(math[iterM++].second);
        while (iterI > cur.y) add(info[--iterI].second);
        while (iterI < cur.y) rem(info[iterI++].second);

        ans[cur.id] = helper.query(cur.z);
    }

    for (int i = 0; i < q; i++) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'int strct::query(int)':
examination.cpp:28:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = nxt; i < sum.size(); i++) ans += sum[i];
      |                           ~~^~~~~~~~~~~~

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