Submission #1297000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297000		chithanhnguyen	Examination (JOI19_examination)	C++20	100 / 100	207 ms	28876 KiB

examination

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

#define int long long
#define S first
#define T second

const int MAXN = 2e5 + 5;
int n, q;
pair<int, int> a[MAXN];

void init() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].S >> a[i].T;
}

namespace subtask1 {
    int query(int x, int y, int z) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i].S >= x && a[i].T >= y && a[i].S + a[i].T >= z)
                ++res;
        }

        return res;
    }

    void solve() {
        for (int queries = 1; queries <= q; ++queries) {
            int x, y, z;
            cin >> x >> y >> z;
            cout << query(x, y, z) << '\n';
        }
    }
}

namespace subtask2 {
    const int MAXA = 1e5 + 1;

    int fen[MAXA + 5], ans[MAXN];

    void update(int idx, int v) {
        for (int i = idx; i <= MAXA; i += i & -i)
            fen[i] += v;
    }

    int get(int idx) {
        int res = 0;
        for (int i = idx; i; i -= i & -i)
            res += fen[i];
        return res;
    }

    struct Data {
        int x, y, id, type;
    };

    void print(const Data& x) {
        cout << x.x << " " << x.y << " " << x.id << " " << x.type << "\n";
    }

    bool cmp(const Data& i, const Data& j) {
        if (i.x == j.x) {
            if (i.type != j.type) return (i.type < j.type);
            return (i.y > j.y);
        }
        return (i.x > j.x);
    }

    void solve() {
        vector<Data> data;
        for (int i = 1; i <= n; ++i) {
            data.push_back({a[i].S + 1, a[i].T + 1, i, 0});
        }

        for (int i = 1; i <= q; ++i) {
            int x, y, z; cin >> x >> y >> z;
            data.push_back({x + 1, y + 1, i, 1});
        }

        sort(data.begin(), data.end(), cmp);

        for (auto &v : data) {
            if (v.type == 0) {
                update(v.y, 1);
            } else {
                int res = get(MAXA) - get(v.y - 1);
                ans[v.id] = res;
            }
            //print(v);
        }

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

namespace subtask3 {
    const int MAXA = 1e5 + 1;
    int fen1[MAXA + 5], fen2[MAXA + 5], ans[MAXN];

    void update1(int idx, int v) {
        for (int i = idx; i <= MAXA; i += i & -i)
            fen1[i] += v;
    }

    int get1(int idx) {
        int res = 0;
        for (int i = idx; i; i -= i & -i)
            res += fen1[i];
        return res;
    }

    void update2(int idx, int v) {
        for (int i = idx; i <= MAXA; i += i & -i)
            fen2[i] += v;
    }

    int get2(int idx) {
        int res = 0;
        for (int i = idx; i; i -= i & -i)
            res += fen2[i];
        return res;
    }

    struct Data {
        int x, y, z, id, type;
    };

    void print(const Data& x) {
        cout << x.x << " " << x.y << " " << x.z << " " << x.id << " " << x.type << "\n";
    }

    bool cmp(const Data& i, const Data& j) {
        if (i.z == j.z) {
            return (i.type < j.type);
        }
        return (i.z > j.z);
    }

    bool cmp2(const Data& i, const Data& j) {
        if (i.x == j.x) {
            if (i.type != j.type) return (i.type < j.type);
            return (i.y > j.y);
        }
        return (i.x > j.x);
    }

    void solve() {
        vector<Data> data, data2;
        for (int i = 1; i <= n; ++i) {
            data.push_back({a[i].S + 1, a[i].T + 1, a[i].S + a[i].T + 2, i, 0});
            data2.push_back({a[i].S + 1, a[i].T + 1, a[i].S + a[i].T + 2, i, 0});
        }

        for (int i = 1; i <= q; ++i) {
            int x, y, z; cin >> x >> y >> z;
            data.push_back({x + 1, y + 1, z + 2, i, 1});
            if (x + y > z) data2.push_back({x + 1, y + 1, z + 2, i, 1});
        }

        sort(data.begin(), data.end(), cmp);

        for (auto &v : data) {
            if (v.type == 0) {
                update1(v.x, 1);
                update2(v.y, 1);
            } else {
                if (v.x + v.y > v.z) continue;
                int total = get2(MAXA) - get2(v.y - 1);
                int out = get1(v.x - 1);
                ans[v.id] = total - out;
            }
        }

        //for (auto &v : data2) print(v);
        sort(data2.begin(), data2.end(), cmp2);

        memset(fen1, 0, sizeof fen1);
        for (auto &v : data2) {
            if (v.type == 0) {
                update1(v.y, 1);
            } else {
                int res = get1(MAXA) - get1(v.y - 1);
                ans[v.id] = res;
            }
        }

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

namespace subtask4 {
    int fen1[MAXN], fen2[MAXN], ans[MAXN];

    vector<int> coordX, coordY;

    int compress(const vector<int>& vec, int x) {
        return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
    }

    void update(int* fen, int idx, int v) {
        for (int i = idx; i < MAXN; i += i & -i)
            fen[i] += v;
    }

    int get(int* fen, int idx) {
        int res = 0;
        for (int i = idx; i; i -= i & -i)
            res += fen[i];
        return res;
    }

    struct Data {
        int x, y, z, id, type;
    };

    bool cmp(const Data& i, const Data& j) {
        if (i.z == j.z) return (i.type < j.type);
        return (i.z > j.z);
    }

    bool cmp2(const Data& i, const Data& j) {
        if (i.x == j.x) {
            if (i.type != j.type) return (i.type < j.type);
            return (i.y > j.y);
        }
        return (i.x > j.x);
    }

    void solve() {
        vector<Data> data, data2;
        vector<int> rawX, rawY;

        for (int i = 1; i <= n; ++i) {
            int x = a[i].S + 1, y = a[i].T + 1, z = a[i].S + a[i].T + 2;
            data.push_back({x, y, z, i, 0});
            data2.push_back({x, y, z, i, 0});
            rawX.push_back(x);
            rawY.push_back(y);
        }

        for (int i = 1; i <= q; ++i) {
            int x, y, z; cin >> x >> y >> z;
            int cx = x + 1, cy = y + 1, cz = z + 2;
            data.push_back({cx, cy, cz, i, 1});
            rawX.push_back(cx);
            rawY.push_back(cy);
            if (x + y > z)
                data2.push_back({cx, cy, cz, i, 1});
        }

        sort(rawX.begin(), rawX.end());
        rawX.erase(unique(rawX.begin(), rawX.end()), rawX.end());
        coordX = rawX;

        sort(rawY.begin(), rawY.end());
        rawY.erase(unique(rawY.begin(), rawY.end()), rawY.end());
        coordY = rawY;

        sort(data.begin(), data.end(), cmp);

        for (auto &v : data) {
            int cx = compress(coordX, v.x);
            int cy = compress(coordY, v.y);
            if (v.type == 0) {
                update(fen1, cx, 1);
                update(fen2, cy, 1);
            } else {
                if (v.x + v.y > v.z) continue;
                int total = get(fen2, MAXN - 1) - get(fen2, cy - 1);
                int out = get(fen1, cx - 1);
                ans[v.id] = total - out;
            }
        }

        memset(fen1, 0, sizeof fen1);

        sort(data2.begin(), data2.end(), cmp2);

        for (auto &v : data2) {
            int cy = compress(coordY, v.y);
            if (v.type == 0) {
                update(fen1, cy, 1);
            } else {
                int res = get(fen1, MAXN - 1) - get(fen1, cy - 1);
                ans[v.id] = res;
            }
        }

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

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    subtask4::solve();

    return 0;
}

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