Submission #1217786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217786		iamhereforfun	Examination (JOI19_examination)	C++20	2 / 100	539 ms	1114112 KiB

examination

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int C = 26;
const int LG = 21;
const int R = 25e3 + 5;
const int B = 450;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

struct Event
{
    int a, b, c, id;
    Event(int q, int w, int e, int r)
    {
        a = q;
        b = w;
        c = e;
        id = r;
    }
    inline bool operator< (Event e)
    {
        if(a == e.a)
        {
            return id < e.id;
        }
        return a > e.a;
    }
};

struct Fenwick2D
{
    vector<vector<int>> ft;
    int n, m;
    Fenwick2D(int ln, int lm)
    {
        n = ln;
        m = lm;
        ft.assign(n + 1, vector<int>(m + 1, 0));
    }
    void update(int pn, int pm, int val)
    {
        while(pn <= n)
        {
            int i = pm;
            while(i <= m)
            {
                ft[pn][i] += val;
                i += LSOne(i);
            }
            pn += LSOne(pn);
        }
    }
    int get(int pn, int pm)
    {
        int sum = 0;
        while(pn > 0)
        {
            int i = pm;
            while(i > 0)
            {
                sum += ft[pn][i];
                i -= LSOne(i);
            }
            pn -= LSOne(pn);
        }
        return sum;
    }
};

int n, q, ans[N];
vector<Event> vec;
vector<int> idb, idc;

void solve()
{
    cin >> n >> q;
    for(int x = 0; x < n; x++)
    {
        int a, b; cin >> a >> b;
        vec.push_back({a, b, a + b, -1});
        idb.push_back(b);
        idc.push_back(a + b);
    }
    for(int x = 0; x < q; x++)
    {
        int a, b, c; cin >> a >> b >> c;
        vec.push_back({a, b, c, x});
        idb.push_back(b);
        idc.push_back(c);
    }
    sort(vec.begin(), vec.end());
    sort(idb.begin(), idb.end());
    idb.erase(unique(idb.begin(), idb.end()), idb.end());
    sort(idc.begin(), idc.end());
    idc.erase(unique(idc.begin(), idc.end()), idc.end());
    Fenwick2D ft(idb.size(), idc.size());
    // for(int i : idb) cout << i << " ";
    // cout << "\n";
    // for(int i : idc) cout << i << " ";
    // cout << "\n";
    // cout << "\n";
    for(Event &e : vec)
    {
        int a = e.a, b = e.b, c = e.c, id = e.id;
        b = lower_bound(idb.begin(), idb.end(), b) - idb.begin() + 1;
        b = idb.size() - b + 1;
        c = lower_bound(idc.begin(), idc.end(), c) - idc.begin() + 1;
        c = idc.size() - c + 1;
        if(id == -1)
        {
            ft.update(b, c, 1);
        }
        else
        {
            ans[id] = ft.get(b, c);
        }
    }
    for(int x = 0; x < q; x++)
    {
        cout << ans[x] << "\n";
    }
}

signed main()
{
    // freopen("CP.INP", "r", stdin);
    // freopen("CP.OUT", "w", stdout);
    // freopen("disrupt.in", "r", stdin);
    // freopen("disrupt.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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