oj.uz

답안 #947748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947748 2024-03-17T01:39:46 Z Pring Examination (JOI19_examination) C++17
41 / 100
 3000 ms 23108 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
typedef array<int, 3> p3i;

const int MXN = 100005, LGC = 32, MXC = 2000000005;
int n, m;
pii a[MXN];
p3i c[MXN];
pii rl[MXN], rr[MXN], rd[MXN];
int ans[MXN];

struct P {
    int t, type, id;
    P() {}
    P(int _t, int _ty, int _id) : t(_t), type(_ty), id(_id) {}
    bool operator<(P o) {
        if (t != o.t) return t < o.t;
        if (type != o.type) return type < o.type;
        return id < o.id;
    }
};

vector<P> swp1, swp2;

struct SMG {
#define mid (((long long) (l + r)) >> 1)
    int val[MXN * LGC], L[MXN * LGC], R[MXN * LGC];
    int nc;

    int new_node() {
        val[nc] = 0;
        L[nc] = 0;
        R[nc] = 0;
        return nc++;
    }

    void init() {
        nc = 1;
        new_node();
    }

    int modify(int id, int l, int r, int p, int v) {
        if (id == 0) id = new_node();
        if (l + 1 == r) {
            val[id] += v;
            return id;
        }
        if (p < mid) L[id] = modify(L[id], l, mid, p, v);
        else R[id] = modify(R[id], mid, r, p, v);
        val[id] = val[L[id]] + val[R[id]];
        return id;
    }

    int query(int id, int l, int r, int _l, int _r) {
        if (_r <= l || r <= _l) return 0;
        if (_l <= l && r <= _r) return val[id];
        return query(L[id], l, mid, _l, _r) + query(R[id], mid, r, _l, _r);
    }

#undef mid
} smg;

void PUT(int id) {
    auto [x, y, z] = c[id];
    rl[id] = mp(0, x);
    swp1.push_back(P(MXC, 1, id));
    if (x + y >= z) {
        rr[id] = mp(x, MXC);
        swp1.push_back(P(y - 1, 2, id));
    } else {
        rr[id] = mp(z - y, MXC);
        swp1.push_back(P(y - 1, 2, id));
        rd[id] = mp(x, z - y);
        swp2.push_back(P(z - 1, 3, id));
    }
}

void RUN(vector<P> &swp) {
    sort(swp.begin(), swp.end());
    smg.init();
    for (auto [t, type, id] : swp) {
        if (type == 0) {
            smg.modify(1, 0, MXC, a[id].fs, 1);
        } else if (type == 1) {
            ans[id] += smg.query(1, 0, MXC, rl[id].fs, rl[id].sc);
        } else if (type == 2) {
            ans[id] += smg.query(1, 0, MXC, rr[id].fs, rr[id].sc);
        } else {
            ans[id] += smg.query(1, 0, MXC, rd[id].fs, rd[id].sc);
        }
    }
}

void SWP1() {
    FOR(i, 0, n) swp1.push_back(P(a[i].sc, 0, i));
    RUN(swp1);
}

void SWP2() {
    FOR(i, 0, n) swp2.push_back(P(a[i].fs + a[i].sc, 0, i));
    RUN(swp2);
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> a[i].fs >> a[i].sc;
    FOR(i, 0, m) cin >> c[i][0] >> c[i][1] >> c[i][2];
    FOR(i, 0, m) PUT(i);
    SWP1();
    SWP2();
    FOR(i, 0, m) cout << n - ans[i] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Execution timed out 3088 ms 8540 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 19248 KB Output is correct
2 Correct 149 ms 20404 KB Output is correct
3 Correct 151 ms 20004 KB Output is correct
4 Correct 148 ms 20248 KB Output is correct
5 Correct 108 ms 17956 KB Output is correct
6 Correct 128 ms 17016 KB Output is correct
7 Correct 136 ms 19780 KB Output is correct
8 Correct 148 ms 18796 KB Output is correct
9 Correct 149 ms 20536 KB Output is correct
10 Correct 102 ms 17332 KB Output is correct
11 Correct 127 ms 20148 KB Output is correct
12 Correct 89 ms 17120 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 19248 KB Output is correct
2 Correct 149 ms 20404 KB Output is correct
3 Correct 151 ms 20004 KB Output is correct
4 Correct 148 ms 20248 KB Output is correct
5 Correct 108 ms 17956 KB Output is correct
6 Correct 128 ms 17016 KB Output is correct
7 Correct 136 ms 19780 KB Output is correct
8 Correct 148 ms 18796 KB Output is correct
9 Correct 149 ms 20536 KB Output is correct
10 Correct 102 ms 17332 KB Output is correct
11 Correct 127 ms 20148 KB Output is correct
12 Correct 89 ms 17120 KB Output is correct
13 Correct 172 ms 23012 KB Output is correct
14 Correct 157 ms 19804 KB Output is correct
15 Correct 146 ms 19124 KB Output is correct
16 Correct 153 ms 22756 KB Output is correct
17 Correct 136 ms 19988 KB Output is correct
18 Correct 112 ms 18376 KB Output is correct
19 Correct 175 ms 23108 KB Output is correct
20 Correct 162 ms 22500 KB Output is correct
21 Correct 180 ms 22520 KB Output is correct
22 Correct 105 ms 16600 KB Output is correct
23 Correct 126 ms 20024 KB Output is correct
24 Correct 88 ms 16568 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Execution timed out 3088 ms 8540 KB Time limit exceeded
5 Halted 0 ms 0 KB -