Submission #1218283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218283		iamhereforfun	Examination (JOI19_examination)	C++20	0 / 100	3095 ms	16148 KiB

examination

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

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

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

struct Fenwick
{
    vector<int> ft;
    int n;
    Fenwick(int len)
    {
        n = len;
        ft.assign(n + 1, 0);
    }
    void update(int pos, int val)
    {
        while(pos <= n)
        {
            ft[pos] += val;
            pos += LSOne(pos);
       }
    }
    int get(int pos)
    {
        int sum = 0;
        while(pos > 0)
        {
            sum += ft[pos];
            pos -= LSOne(pos);
        }
        return sum;
    }
    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
} fta(N), ftb(N);

int n, q, num = 0, ans[N];
vector<array<int, 4>> event;
vector<int> ida, idb, idc;

void solve()
{
    cin >> n >> q;
    for(int x = 0; x < n; x++)
    {
        int a, b; cin >> a >> b;
        event.push_back({a + b, (int)1e9, a, b});
        ida.push_back(a);
        idb.push_back(b);
        idc.push_back(a + b);
    }
    for(int x = 0; x < q; x++)
    {
        int a, b, c; cin >> a >> b >> c;
        event.push_back({max(c, a + b), x, a, b});
        ida.push_back(a);
        idb.push_back(b);
        idc.push_back(max(c, a + b));
    }
    sort(idb.begin(), idb.end());
    idb.erase(unique(idb.begin(), idb.end()), idb.end());
    sort(ida.begin(), ida.end());
    ida.erase(unique(ida.begin(), ida.end()), ida.end());
    sort(idc.begin(), idc.end());
    idc.erase(unique(idc.begin(), idc.end()), idc.end());
    sort(event.rbegin(), event.rend());
    for(array<int, 4> a : event)
    {
        if(a[1] == 1e9)
        {
            num++;
            fta.update(a[2], 1);
            ftb.update(a[3], 1);
        }
        else
        {
            ans[a[1]] = num - fta.get(a[2] - 1) - ftb.get(a[3] - 1);
        }
    }
    for(int x = 0; x < q; x++)
    {
        cout << ans[x] << " ";
    }
}

signed main()
{
    // freopen("CP.INP", "r", stdin);
    // freopen("CP.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: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57