Submission #157174

#	Time	Username	Problem	Language	Result	Execution time	Memory
157174		Flying_dragon_02	Examination (JOI19_examination)	C++14	100 / 100	2192 ms	157796 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int inf = 1e9 + 1;

const int N = 1e5 + 5;

vector<int> f[2 * N], bit[2 * N];

vector<pair<int, ii>> Sd;

vector<int> X, Y;

vector<pair<ii, ii>> E;

int n, q, ans[N];

void fakeup(int a, int b) {
    int x = lower_bound(X.begin(), X.end(), a) - X.begin();
    while(x > 0) {
        int y = lower_bound(Y.begin(), Y.end(), b) - Y.begin();
        while(y > 0) {
            f[x].pb(y);
            y -= y & (-y);
        }
        x -= x & (-x);
    }
}

void fakeget(int a, int b) {
    int x = lower_bound(X.begin(), X.end(), a) - X.begin();
    while(x < 2 * N) {
        int y = lower_bound(Y.begin(), Y.end(), b) - Y.begin();
        while(y < Y.size()) {
            f[x].pb(y);
            y += y & (-y);
        }
        x += x & (-x);
    }
}

void up(int a, int b) {
   // a = lower_bound(X.begin(), X.end(), a) - X.begin();
    b = lower_bound(Y.begin(), Y.end(), b) - Y.begin();
    int x = lower_bound(X.begin(), X.end(), a) - X.begin();
    while(x > 0) {
        int y = lower_bound(f[x].begin(), f[x].end(), b) - f[x].begin();
        while(y > 0) {
            bit[x][y]++;
            y -= y & (-y);
        }
        x -= x & (-x);
    }
}

int get(int a, int b) {
    //a = lower_bound(X.begin(), X.end(), a) - X.begin();
    b = lower_bound(Y.begin(), Y.end(), b) - Y.begin();
    int sum = 0;
    int x = lower_bound(X.begin(), X.end(), a) - X.begin();
    while(x < 2 * N) {
        int y = lower_bound(f[x].begin(), f[x].end(), b) - f[x].begin();
        //cout << y << " " << f[x].size() << "\n";
        while(y < f[x].size()) {
           // cout << x << " " << y << " " << bit[x].size() << " " << X.size() << "\n";
            sum += bit[x][y];
            y += y & (-y);
        }
        x += x & (-x);
    }
    return sum;
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    for(int i = 0; i < 2 * N; i++)
        f[i].pb(-1);
    cin >> n >> q;
    X.pb(-1);
    Y.pb(-1);
    for(int i = 1; i <= n; i++) {
        int s, t;
        cin >> s >> t;
        int val = s + t;
        X.pb(s);
        Y.pb(t);
        Sd.pb({val, {s, t}});
    }
    sort(Sd.begin(), Sd.end());
    for(int i = 1; i <= q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        X.pb(x);
        Y.pb(y);
        E.pb({{z, i}, {x, y}});
    }
    sort(E.begin(), E.end());
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    int ptr = Sd.size() - 1;
    for(int i = E.size() - 1; i >= 0; i--) {
        while(ptr >= 0 && E[i].fi.fi <= Sd[ptr].fi) {
            fakeup(Sd[ptr].se.fi, Sd[ptr].se.se);
            ptr--;
        }
        fakeget(E[i].se.fi, E[i].se.se);
    }
    for(int i = 0; i < 2 * N; i++) {
        sort(f[i].begin(), f[i].end());
        f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end());
        bit[i].resize(f[i].size() + 5, 0);
    }
    ptr = Sd.size() - 1;
    for(int i = E.size() - 1; i >= 0; i--) {
        while(ptr >= 0 && E[i].fi.fi <= Sd[ptr].fi) {
            up(Sd[ptr].se.fi, Sd[ptr].se.se);
            ptr--;
        }
        ans[E[i].fi.se] = get(E[i].se.fi, E[i].se.se);
    }
    for(int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'void fakeget(int, int)':
examination.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(y < Y.size()) {
               ~~^~~~~~~~~~
examination.cpp: In function 'int get(int, int)':
examination.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(y < f[x].size()) {
               ~~^~~~~~~~~~~~~

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