Submission #839433

#	Time	Username	Problem	Language	Result	Execution time	Memory
839433		CDuong	Examination (JOI19_examination)	C++17	100 / 100	550 ms	41140 KiB

examination

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define vvi vector<vi>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

struct point {
    int x, y, sum, idx;
    
    point(int x, int y, int sum, int idx = 0) : x(x), y(y), sum(sum), idx(idx) {}

    bool operator < (const point &o) const {
        return x < o.x;
    }
};

struct FenwickTree2D {
    int n;
    vvi data;
    vvi BIT;

    FenwickTree2D(int n) : n(n) {
        BIT.resize(n + 1);
        data.resize(n + 1);
    }

    void fupdate(int x, int y) {
        for (; x <= n; x += x & -x)
            data[x].emplace_back(y);
    }

    void fget(int x, int y) {
        for (; x > 0; x -= x & -x)
            data[x].emplace_back(y);
    }

    void initBIT() {
        for (int i = 1; i <= n; ++i) {
            sort(all(data[i]));
            BIT[i].resize(isz(data[i]) + 1);
        }
    }

    void update(int x, int yy, int val) {
        for (; x <= n; x += x & -x) {
            int y = lower_bound(all(data[x]), yy) - data[x].begin() + 1;
            for (; y <= isz(data[x]); y += y & -y)
                BIT[x][y] += val;
        }
    }

    int get(int x, int yy) {
        int res = 0;
        for (; x; x -= x & -x) {
            int y = lower_bound(all(data[x]), yy) - data[x].begin() + 1;
            for (; y > 0; y -= y & -y)
                res += BIT[x][y];
        }
        return res;
    }
};

vi r, c;
int n, q, ans[mxN];
vector<point> a, qq;

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        x = -x, y = -y;
        r.emplace_back(y);
        c.emplace_back(x + y);
        a.emplace_back(x, y, x + y);
    }
    for (int i = 1; i <= q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        x = -x, y = -y, z = -z;
        r.emplace_back(y);
        c.emplace_back(z);
        qq.emplace_back(x, y, z, i);
    }
    
    sort(all(a)); sort(all(qq));
    sort(all(r)); r.erase(unique(all(r)), r.end());
    sort(all(c)); c.erase(unique(all(c)), c.end());

    FenwickTree2D fenw(isz(r));
    for (auto &[x, y, sum, idx] : a) {
        y = lower_bound(all(r), y) - r.begin() + 1;
        sum = lower_bound(all(c), sum) - c.begin() + 1;
        fenw.fupdate(y, sum);
    }
    for (auto &[x, y, sum, idx] : qq) {
        y = lower_bound(all(r), y) - r.begin() + 1;
        sum = lower_bound(all(c), sum) - c.begin() + 1;
        fenw.fget(y, sum);
    }
    fenw.initBIT();

    int ptr = 0;
    for (int i = 0; i < q; ++i) {
        auto [x, y, sum, idx] = qq[i];
        while (ptr < n && a[ptr].x <= x) {
            fenw.update(a[ptr].y, a[ptr].sum, 1);
            ++ptr;
        }
        ans[idx] = fenw.get(y, sum);
    }

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

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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