Submission #527710

#	Time	Username	Problem	Language	Result	Execution time	Memory
527710		4fecta	Examination (JOI19_examination)	C++17	100 / 100	1045 ms	68312 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

struct pt {
    int x, y, z, t;
};

bool cmp(pt p, pt q) {
    if (p.z == q.z) return p.t > q.t;
    return p.z < q.z;
}

bool cmp1(pt p, pt q) {
    if (p.x != q.x) return p.x < q.x;
    return p.y < q.y;
}

const int MN = 200005;

int n, q, x, y, z, ans[MN], bit[MN];
vector<int> xs, ys, zs, upds;
map<int, int> mx, my, mz;
vector<pt> v;

void upd(int x, int val) {
    if (val > 0) upds.push_back(x);
    for (int i = x; i < MN; i += i & -i) bit[i] += val;
}

void clear() {
    for (int x : upds) upd(x, -1);
    upds.clear();
}

int qry(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) ret += bit[i];
    return ret;
}

void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    vector<pt> ps, qs;
    for (int i = l; i <= mid; i++) if (v[i].t) qs.push_back(v[i]);
    for (int i = mid + 1; i <= r; i++) if (!v[i].t) ps.push_back(v[i]);
    sort(ps.begin(), ps.end(), cmp1);
    sort(qs.begin(), qs.end(), cmp1);
    int ptr = ps.size() - 1;
    for (int i = qs.size() - 1; i >= 0; i--) {
        while (ptr >= 0 && ps[ptr].x >= qs[i].x) upd(ps[ptr--].y, 1);
        ans[qs[i].t] += qry(MN - 1) - qry(qs[i].y - 1);
    }
    clear();
    solve(l, mid), solve(mid + 1, r);
}

int32_t main() {
    boost();

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        z = x + y;
        xs.push_back(x);
        ys.push_back(y);
        zs.push_back(z);
        v.push_back({x, y, z, 0});
    }
    for (int i = 1; i <= q; i++) {
        cin >> x >> y >> z;
        xs.push_back(x);
        ys.push_back(y);
        zs.push_back(z);
        v.push_back({x, y, z, i});
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(zs.begin(), zs.end());
    zs.erase(unique(zs.begin(), zs.end()), zs.end());
    for (int i = 0; i < xs.size(); i++) mx[xs[i]] = i + 1;
    for (int i = 0; i < ys.size(); i++) my[ys[i]] = i + 1;
    for (int i = 0; i < zs.size(); i++) mz[zs[i]] = i + 1;
    for (int i = 0; i < v.size(); i++) v[i].x = mx[v[i].x], v[i].y = my[v[i].y], v[i].z = mz[v[i].z];
    sort(v.begin(), v.end(), cmp);
    solve(0, v.size() - 1);
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);

    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int32_t main()':
examination.cpp:90:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < xs.size(); i++) mx[xs[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
examination.cpp:91:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < ys.size(); i++) my[ys[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
examination.cpp:92:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < zs.size(); i++) mz[zs[i]] = i + 1;
      |                     ~~^~~~~~~~~~~
examination.cpp:93:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < v.size(); i++) v[i].x = mx[v[i].x], v[i].y = my[v[i].y], v[i].z = mz[v[i].z];
      |                     ~~^~~~~~~~~~

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