제출 #1309382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309382		kolio642	Examination (JOI19_examination)	C++20	100 / 100	768 ms	46332 KiB

examination

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

struct SegmentTree
{
    struct node
    {
        int l, r;
        long long data;

        node()
        {
            l = r = -1;
            data = 0;
        }

        node(long long  _data, int _l = -1, int _r = -1)
        {
            data = _data;
            l = _l;
            r = _r;
        }
    };

    int l, r;
    vector <node> a;

    SegmentTree()
    {
        l = r = -1;
        a.emplace_back();
    }

    void make_r(int node)
    {
        a[node].r = a.size();
        a.emplace_back();
    }

    void make_l(int node)
    {
        a[node].l = a.size();
        a.emplace_back();
    }

    void calc(int node)
    {
        long long dataL, dataR;

        if(a[node].l == -1)
            dataL = 0;
        else
            dataL = a[a[node].l].data;

        if(a[node].r == -1)
            dataR = 0;
        else
            dataR = a[a[node].r].data;

        a[node].data = dataL + dataR;
    }

    void update(int node, int l, int r, int qpos, long long qval)
    {
        if(l == r)
        {
            a[node].data += qval;
            return;
        }

        int mid = l + (r - l) / 2;

        if(qpos <= mid)
        {
            if(a[node].l == -1)
                make_l(node);
            update(a[node].l, l, mid, qpos, qval);
        }
        else
        {
            if(a[node].r == -1)
                make_r(node);
            update(a[node].r, mid + 1, r, qpos, qval);
        }

        calc(node);
    }

    long long query(int node, int l, int r, int ql, int qr)
    {
        if(ql <= l && qr >= r)
            return a[node].data;
        if(r < ql || l > qr)
            return 0;

        int mid = l + (r - l) / 2;
        long long ans = 0;

        if(a[node].l != -1)
            ans += query(a[node].l, l, mid, ql, qr);

        if(a[node].r != -1)
            ans += query(a[node].r, mid + 1, r, ql, qr);

        return ans;
    }
};

struct grade
{
    int a, b, idx;
    long long sum;
    bool isQuery;
    int queryIdx;

    grade()
    {
        a = b = idx = 0;
        sum = 0;
        isQuery = false;
    }
    grade(int _a, int _b, int _sum, bool _isQuery, int _idx)
    {
        a = _a;
        b = _b;
        sum = _sum;
        isQuery = _isQuery;
        idx = _idx;
    }
};

const int MAXN = (int)1e5 + 5;

grade q[2 * MAXN];
int ans[2 * MAXN];
grade v[2 * MAXN];
SegmentTree tree;
int n, q1;

bool cmp1(const grade &g1,const grade &g2)
{
    if(g1.a == g2.a)
        return g1.isQuery < g2.isQuery;
    else
        return (g1.a > g2.a);
}

bool cmp2(const grade &g1, const grade &g2)
{
    if(g1.b == g2.b)
        return g1.isQuery < g2.isQuery;
    else
        return (g1.b > g2.b);
}

void read()
{
    cin >> n >> q1;

    int x, y, z;

    for(int i = 0; i < n ; i++)
    {
        cin >> x >> y;

        q[i] = {x, y, x + y, 0, -1};
    }

    for(int i = n; i < n + q1; i++)
    {
        cin >> x >> y >> z;

        q[i] = {x, y, z, 1, -1};
        q[i].queryIdx = i - n;
    }

    sort(q, q + n + q1, cmp1);

    //for(int i = 0 ; i < n + q1; i++)
    //    cout << q[i].a << ' ' << q[i].b << ' ' << q[i].isQuery << endl;
}

void devide(int l, int r)
{
    if(l == r)
        return;

    int mid = (l + r) / 2;

    devide(l, mid);
    devide(mid + 1, r);

    for(int i = l; i <= r; i++)
    {
        q[i].idx = i;
        v[i] = q[i];
    }

    sort(v + l, v + r + 1, cmp2);

    for(int i = l; i <= r; i++)
    {
        if(v[i].isQuery == 0)
        {
            if(v[i].idx <= mid)
                tree.update(0, 0, 2e9, v[i].sum, +1);
        }
        else
        {
            if(v[i].idx > mid)
                ans[v[i].queryIdx] += tree.query(0, 0, 2e9, v[i].sum, 2e9);
        }
    }

    tree.a.clear();
    tree.a.emplace_back();
}

int main()
{
    speed();

    read();

    devide(0, n + q1 - 1);

    for(int i = 0; i < q1; i++)
    {
        cout << ans[i] << '\n';
    }

    return 0;
}

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