Submission #709343

#	Time	Username	Problem	Language	Result	Execution time	Memory
709343		Johann	Examination (JOI19_examination)	C++14	2 / 100	3005 ms	13076 KiB

examination

// TODO: Still to solve...
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

struct Req
{
    ll a, b, c;
    int idx;
};

struct SqrtDecom
{
    vpii newStuff;
    vvpii buckets;
    vi minele;
    int sq;
    void init(int N)
    {
        sq = ceil(sqrt(N));
    }
    void insert(pii &item)
    {
        newStuff.push_back(item);
        if (sz(newStuff) == sq)
        {
            for (int i = 0; i < sz(buckets); ++i)
            {
                for (pii tmp : buckets[i])
                    newStuff.push_back(tmp);
                buckets[i].clear();
            }
            buckets.push_back(vpii());
            minele.push_back(0);
            sort(all(newStuff));

            for (int i = 0; i < sz(newStuff); ++i)
                buckets[i / sq].push_back(newStuff[i]);
            newStuff.clear();

            for (int i = 0; i < sz(buckets); ++i)
            {
                minele[i] = buckets[i].front().first;
                sort(all(buckets[i]), [&](pii &a, pii &b)
                     { return a.second < b.second; });
            }
        }
    }

    int answer(Req &q)
    {
        int ans = 0;
        for (pii r : newStuff)
            if (r.first >= q.a && r.second >= q.b)
                ++ans;
        int idx = sz(buckets) - 1;
        while (idx >= 0 && minele[idx] >= q.a)
        {
            ans += buckets[idx].end() - lower_bound(all(buckets[idx]), make_pair(0LL, q.b), [&](const pii a, const pii b)
                                                    { return a.second < b.second; });
            idx--;
        }
        if (idx != -1)
            for (pii r : buckets[idx])
                if (r.first >= q.a && r.second >= q.b)
                    ++ans;
        return ans;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;

    vpii ST(N); // A <= S[i] , B <= T[i], C <= S[i] + T[i]
    for (int i = 0; i < N; ++i)
        cin >> ST[i].first >> ST[i].second;

    vector<Req> Queries(Q);
    for (int i = 0, a, b, c; i < Q; ++i)
    {
        cin >> a >> b >> c;
        Queries[i] = {a, b, c, i};
    }
    vi ans(Q);

    sort(all(Queries), [&](Req &a, Req &b)
         { return a.c > b.c; });
    sort(all(ST), [&](pii &a, pii &b)
         { return a.first + a.second > b.first + b.second; });

    SqrtDecom sqd;
    sqd.init(N);

    int idx = 0;
    for (int i = 0; i < sz(Queries); ++i)
    {
        while (idx < sz(ST) && ST[idx].first + ST[idx].second >= Queries[i].c)
        {
            sqd.insert(ST[idx]);
            ++idx;
        }
        ans[Queries[i].idx] = sqd.answer(Queries[i]);
    }

    for (int x : ans)
        cout << x << "\n";

    return 0;
}

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