Submission #1271375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271375		ngocphu	Examination (JOI19_examination)	C++20	100 / 100	143 ms	16652 KiB

examination

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxN = 2e5 + 30;

int n, q, bit[4][400053], ans[maxN];
vector<int> b, vec;

void update(int x, int v, int type)
{
    for (; x <= 400050; x += x & -x) bit[type][x] += v;
}

int get(int x, int type)
{
    int res = 0;
    for (; x >= 1; x -= x & -x) res += bit[type][x];
    return res;
}

struct dataa
{
    int s, t, id;
};

dataa a[maxN], a_s[maxN], a_t[maxN];

struct cmpS
{
    bool operator() (dataa a, dataa b)
    {
        return a.s > b.s;
    }
};

struct cmpT
{
    bool operator() (dataa a, dataa b)
    {
        return a.t > b.t;
    }
};

struct Data
{
    int x, y, z, id;
};

vector<Data> query1, query2;

struct cmpY
{
    bool operator() (Data a, Data b)
    {
        return a.y > b.y;
    }
};

struct cmpZ1
{
    bool operator() (Data a, Data b)
    {
        return a.z > b.z;
    }
};

struct Dataa
{
    int s, t, sum, id;
};

Dataa a_sum[maxN];

struct cmpZ2
{
    bool operator() (Dataa a, Dataa b)
    {
        return a.sum > b.sum;
    }
};

int fi(int x)
{
    int l = 1, r = n, ans = 0;

    while(l <= r)
    {
        int m = (l + r) / 2;

        if (a_s[m].s >= x)
        {
            ans = m;
            l = m + 1;
        }
        else r = m - 1;
    }

    return ans;
}

int fi2(int x)
{
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen(".INP","r",stdin);
    // freopen(".OUT","w",stdout);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        int s, t; cin >> s >> t;

        a[i] = dataa({s, t, i});
        a_s[i] = dataa({s, t, i});
        a_sum[i] = Dataa({s, t, s + t, i});

        b.push_back(s);
        b.push_back(t);
    }

    for (int i = 1; i <= q; ++i)
    {
        int x, y, z; cin >> x >> y >> z;

        if (x + y >= z) query1.push_back(Data({x, y, z, i}));
        else
        {
            b.push_back(x);
            b.push_back(y);
            query2.push_back(Data({x, y, z, i}));
        }
    }

    // sub 2

    sort(a_s + 1, a_s + n + 1, cmpS());

    for (int i = 1; i <= n; ++i)
    {
        a_t[i] = a_s[i];
        a_t[i].id = i;
    }

    sort(a_t + 1, a_t + n + 1, cmpT());

    if (!query1.empty()) sort(query1.begin(), query1.end(), cmpY());

    int j = 1;
    for (int i = 0; i < query1.size(); ++i)
    {
        int x = query1[i].x, y = query1[i].y, z = query1[i].z, id = query1[i].id;
        while(j <= n && a_t[j].t >= y)
        {
            int pos = a_t[j].id;
            update(pos, 1, 1);
            j++;
        }

        int r = fi(x);

        if (r == 0) continue;

        ans[id] = get(r, 1);
    }

    // sub 34

    sort(b.begin(), b.end());
    vec.push_back(b[0]);

    for (int i = 1; i < b.size(); ++i)
        if (vec.back() != b[i])
            vec.push_back(b[i]);

    for (int i = 1; i <= n; ++i)
    {
        int s = a_sum[i].s;
        int t = a_sum[i].t;

        a_sum[i].s = fi2(s);
        a_sum[i].t = fi2(t);
    }

    for (int i = 0; i < query2.size(); ++i)
    {
        int x = query2[i].x;
        int y = query2[i].y;

        query2[i].x = fi2(x);
        query2[i].y = fi2(y);
    }

    sort(a_sum + 1, a_sum + n + 1, cmpZ2());
    if (!query2.empty()) sort(query2.begin(), query2.end(), cmpZ1());

    j = 1;

    for (int i = 0; i < query2.size(); ++i)
    {
        int x = query2[i].x, y = query2[i].y, z = query2[i].z, id = query2[i].id;

        while(j <= n && a_sum[j].sum >= z)
        {
            int s = a_sum[j].s;
            int t = a_sum[j].t;
            update(s, 1, 2);
            update(t, 1, 3);
            j++;
        }

        int math = get(400050, 2) - get(x - 1, 2);
        int info = get(400050, 3) - get(y - 1, 3);
        int cnt = j - 1;

        ans[id] = math + info - cnt;
    }

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

    return 0;
}

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