Submission #709435

#	Time	Username	Problem	Language	Result	Execution time	Memory
709435		Johann	Examination (JOI19_examination)	C++14	100 / 100	2062 ms	14384 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;
    vpii stuff;
    vvpii buckets;
    vi minele;
    int sq;
    void init(int N)
    {
        sq = 2 * ceil(sqrt(N));
    }
    void insert(pii &item)
    {
        newStuff.push_back(item);
        if (sz(newStuff) == sq)
        {
            for (pii tmp : newStuff)
                stuff.push_back(tmp);
            newStuff.clear();
            sort(all(stuff));
            buckets.push_back(vpii(sq));
            minele.push_back(0);

            for (int i = 0; i < sz(buckets); ++i)
            {
                minele[i] = stuff[i * sq].first;
                sort(stuff.begin() + i * sq, stuff.begin() + (i + 1) * sq, [&](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(stuff) / sq - 1;
        while (idx >= 0 && minele[idx] >= q.a)
        {
            ans += (stuff.begin() + (idx + 1) * sq) - lower_bound(stuff.begin() + idx * sq, stuff.begin() + (idx + 1) * sq, make_pair(0LL, q.b), [&](const pii a, const pii b)
                                                                  { return a.second < b.second; });
            --idx;
        }
        if (idx != -1)
            for (int i = idx * sq; i < (idx + 1) * sq; ++i)
                if (stuff[i].first >= q.a && stuff[i].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: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57