oj.uz

Submission #554008

# Submission time Handle Problem Language Result Execution time Memory
554008 2022-04-27T14:34:15 Z AA_Surely Examination (JOI19_examination) C++17
2 / 100
 123 ms 8576 KB 
#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 long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 1e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int SQ = 200;

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];
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});
    gooni.clear();

    F0R(i, SQ) sort(ALL(keep[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 += keep[i].size() - (lower_bound(ALL(keep[i]), PII(qs[p].mb, 0)) - keep[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() >= SQ) rebuild();

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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 7 ms 464 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 6 ms 444 KB Output is correct
11 Correct 16 ms 504 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 7 ms 532 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 7 ms 516 KB Output is correct
16 Correct 11 ms 556 KB Output is correct
17 Correct 7 ms 468 KB Output is correct
18 Correct 4 ms 560 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 8576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 8576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 7 ms 464 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 6 ms 444 KB Output is correct
11 Correct 16 ms 504 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 7 ms 532 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 7 ms 516 KB Output is correct
16 Correct 11 ms 556 KB Output is correct
17 Correct 7 ms 468 KB Output is correct
18 Correct 4 ms 560 KB Output is correct
19 Runtime error 123 ms 8576 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -