Submission #1169882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169882		chikien2009	Examination (JOI19_examination)	C++20	100 / 100	139 ms	8008 KiB

examination

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class FENWICK_TREE
{
    private:
    int tree_size;
    vector<int> tree;
    public:
    inline FENWICK_TREE(int new_size)
    {
        tree_size = new_size;
        tree.resize(tree_size + 1, 0);
    }
    inline void Update(int pos, int val)
    {
        while (pos <= tree_size)
        {
            tree[pos] += val;
            pos += pos & (~(pos - 1));
        }
    }
    inline int Get(int pos)
    {
        int res = 0;
        while (0 < pos)
        {
            res += tree[pos];
            pos -= pos & (~(pos - 1));
        }
        return res;
    }
} ft1(200000), ft2(200000);

array<int, 4> v[200000];
int n, q, a, b, c, d, all[200000], all_a[200000], all_b[200000];

int main()
{
    setup();

    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        v[i] = {a + b, 1000000, a, b};
        all_a[i] = a;
        all_b[i] = b;
        all[i] = a + b;
    }
    for (int i = 0; i < q; ++i)
    {
        cin >> a >> b >> c;
        v[i + n] = {max(a + b, c), i, a, b};
        all[i + n] = max(a + b, c);
        all_a[i + n] = a;
        all_b[i + n] = b;
    }
    n += q;
    sort(v, v + n);
    sort(all, all + n);
    a = unique(all, all + n) - all;
    for (int i = 0; i < n; ++i)
    {
        v[i][0] = lower_bound(all, all + a, v[i][0]) - all + 1;
    }
    sort(all_a, all_a + n);
    a = unique(all_a, all_a + n) - all_a;
    for (int i = 0; i < n; ++i)
    {
        v[i][2] = lower_bound(all_a, all_a + a, v[i][2]) - all_a + 1;
    }
    sort(all_b, all_b + n);
    a = unique(all_b, all_b + n) - all_b;
    for (int i = 0; i < n; ++i)
    {
        v[i][3] = lower_bound(all_b, all_b + a, v[i][3]) - all_b + 1;
    }
    a = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        if (v[i][1] == 1000000)
        {
            a++;
            ft1.Update(v[i][2], 1);
            ft2.Update(v[i][3], 1);
        }
        else
        {
            all[v[i][1]] = a - ft1.Get(v[i][2] - 1) - ft2.Get(v[i][3] - 1);
        }
    }
    for (int i = 0; i < q; ++i)
    {
        cout << all[i] << "\n";
    }
    return 0;
}

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