제출 #554016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554016		AA_Surely	Examination (JOI19_examination)	C++14	2 / 100	3092 ms	6948 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 WTF 		cout << "WTF" << endl

#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 = 1000;

struct Tutee {
    int a, b, c;

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

} ns[N];

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

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

int n, q;
VPII keep[SQ];
VI kp[SQ];
vector<Tutee> gooni;
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();

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

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

    return;
}

inline void rebuild() {
    for(const Tutee &t : gooni) {
        keep[t.a / SQ].pb({t.b, t.a});
        kp[t.a / SQ].pb(t.b);
    }

    gooni.clear();

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

    return;
}

inline int getKeep(int p) {
    int dasti = qs[p].ma / SQ;

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

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

inline int getGooni(int p) {
    int ret = 0;
    for(const Tutee &on : gooni)
        ret += (on.a >= qs[p].ma && on.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.emplace_back(ns[ptr++]);
        if (gooni.size() >= TOF) rebuild();

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

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

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