Submission #554041

#	Time	Username	Problem	Language	Result	Execution time	Memory
554041		AA_Surely	Examination (JOI19_examination)	C++14	0 / 100	3078 ms	7248 KiB

examination

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;

typedef pair<int, int> 	PII;
typedef vector<int> 	VI;
typedef vector<PII> 	VPII;

const int N = 1e5 + 7;
const int SQ = 320;
const int TOF = 500;

struct Tutee {
    int a, b, c;

    inline bool operator < (const Tutee &other) {
        return c > other.c;
    }

} ns[N], gooni[N];

struct Query {
    int ma, mb, mc, id;

    inline bool operator < (const Query &other) {
        return mc > other.mc;
    }
} qs[N];

int n, q, sz;
VPII keep[SQ];
VI kp[SQ];
PII whole[N];
int ans[N];

void init() {
    cin >> n >> q;
    VI comp;

    F0R(i, n) {
        cin >> ns[i].a >> ns[i].b;
        ns[i].c = ns[i].a + ns[i].b;
    }

    F0R(i, q) {
        cin >> qs[i].ma >> qs[i].mb >> qs[i].mc;
        qs[i].id = i;
    }

    comp.resize(n);
    F0R(i, n) comp[i] = ns[i].a;
    sort(ALL(comp));
    comp.resize(unique(ALL(comp)) - comp.begin());
    F0R(i, n) ns[i].a = lower_bound(ALL(comp), ns[i].a) - comp.begin();
    F0R(i, q) qs[i].ma = lower_bound(ALL(comp), qs[i].ma) - comp.begin();

    return;
}

inline void rebuild() {
    int pt = 0;
    F0R(i, SQ) {
        for(const PII &on : keep[i]) whole[pt++] = on;
        keep[i].clear();
        kp[i].clear();
    }

    F0R(i, sz) whole[pt++] = PII(gooni[i].a, gooni[i].b);
    sz = 0;

    sort(whole, whole + pt);
    
    F0R(i, pt) {
        keep[i / SQ].pb(whole[i]);
        kp[i / SQ].pb(whole[i].S);
    }

    F0R(i, SQ) sort(ALL(kp[i]));

    return;
}

inline int getKeep(int p) {
    int dasti = SQ - 1;
    F0R(i, SQ) if (!keep[i].empty() && keep[i][0].F >= qs[p].ma) {
        dasti = i - 1;
        break;
    }

    int ret = 0, ret2 = 0;
    if (dasti >= 0) 
        for(const PII &on : keep[dasti]) 
            ret += (on.F >= qs[p].ma && on.S >= qs[p].mb);

    FOR(x, max(0, dasti), SQ)
        for(const PII &on : keep[x]) 
            ret2 += (on.F >= qs[p].ma && on.S >= qs[p].mb);

    FOR(i, dasti + 1, SQ) ret += kp[i].size() - (lower_bound(ALL(kp[i]), qs[p].mb) - kp[i].begin());

    assert(ret == ret2);
    return ret;
}

inline int getGooni(int p) {
    int ret = 0;
    F0R(i, sz)
        ret += (gooni[i].a >= qs[p].ma && gooni[i].b >= qs[p].mb);
    return ret;
}

int main() {
    IOS;
    
    init();
    sort(qs, qs + q);
    sort(ns, ns + n);
    
    int ptr = 0;
    F0R(i, q) {
        while(ptr < n && ns[ptr].c >= qs[i].mc) gooni[sz++] = ns[ptr++];
        if (sz >= TOF) rebuild();

        ans[ qs[i].id ] = getKeep(i) + getGooni(i);
    }

    F0R(i, q) cout << ans[i] << '\n';
    return 0;
}

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