oj.uz

Submission #722481

# Submission time Handle Problem Language Result Execution time Memory
722481 2023-04-12T05:50:55 Z saayan007 Examination (JOI19_examination) C++17
20 / 100
 98 ms 10820 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define fr first
#define sc second
#define eb emplace_back
#define nl "\n"

struct BIT { // fenwick tree
    int n;
    vector<int> a;

    BIT(int N) {
        n = N - 1;
        a.resize(N, 0);
    }

    void mod(int x, int v) {
        while(x <= n) {
            a[x] += v;
            x += x&-x;
        }
    }

    int qry(int x) {
        x = min(x, n);
        int v = 0;
        while(x >= 1) {
            v += a[x];
            x -= x&-x;
        }
        return v;
    }

    int qry(int x, int y) {
        return qry(y) - qry(x - 1);
    }
};

const int N = 1e5L + 1;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    pair<int, int> s[n + 1];
    for(int i = 1; i <= n; ++i) {
        cin >> s[i].fr >> s[i].sc;
    }

    pair<pair<int, int>, int> q[m];
    for(int i = 0; i < m; ++i) {
        cin >> q[i].fr.sc >> q[i].fr.fr;
        int trash; cin >> trash;
        q[i].sc = i;
    }

    sort(q, q + m);
    reverse(q, q + m);

    sort(s + 1, s + n + 1);
    pair<int, int> t[n + 1];
    for(int i = 1; i <= n; ++i)
        t[i] = {s[i].sc, i};

    sort(t + 1, t + n + 1);
    reverse(t + 1, t + n + 1);

    BIT bit(n + 1);

    /* cout << "students\n"; */
    /* for(int i = 1; i <=n; ++i) */
    /*     cout << s[i].fr << ' ' << s[i].sc << nl; */
    /* cout << nl; */
    /* cout << "secondary marks\n"; */
    /* for(int i = 1; i <= n; ++i) */
    /*     cout << t[i].fr << ' ' << t[i].sc << nl; */
    /* cout << nl; */

    /* cout << "queries\n"; */
    int ans[m];
    int j = 0;
    for(auto u : q) {
        int y = u.fr.fr, x = u.fr.sc, idx = u.sc;
        /* cout << x << ' ' << y << nl; */

        while(j + 1 <= n && t[j + 1].fr >= y) {
            bit.mod(t[++j].sc, 1);
        }    
        /* for(int i = 1; i<=n; ++i) */
            /* cout << bit.qry(i, i) << ' '; */
        /* cout << nl << nl; */

        int j = lower_bound(s + 1, s + n + 1, make_pair(x, -1LL)) - s;
        ans[idx] = bit.qry(j, n);
    }

    for(auto u : ans)
        cout << u << nl;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7960 KB Output is correct
2 Correct 98 ms 10328 KB Output is correct
3 Correct 96 ms 10372 KB Output is correct
4 Correct 72 ms 9664 KB Output is correct
5 Correct 69 ms 9680 KB Output is correct
6 Correct 57 ms 8936 KB Output is correct
7 Correct 80 ms 10324 KB Output is correct
8 Correct 87 ms 10268 KB Output is correct
9 Correct 80 ms 10224 KB Output is correct
10 Correct 73 ms 9404 KB Output is correct
11 Correct 79 ms 9412 KB Output is correct
12 Correct 51 ms 8488 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7960 KB Output is correct
2 Correct 98 ms 10328 KB Output is correct
3 Correct 96 ms 10372 KB Output is correct
4 Correct 72 ms 9664 KB Output is correct
5 Correct 69 ms 9680 KB Output is correct
6 Correct 57 ms 8936 KB Output is correct
7 Correct 80 ms 10324 KB Output is correct
8 Correct 87 ms 10268 KB Output is correct
9 Correct 80 ms 10224 KB Output is correct
10 Correct 73 ms 9404 KB Output is correct
11 Correct 79 ms 9412 KB Output is correct
12 Correct 51 ms 8488 KB Output is correct
13 Incorrect 93 ms 10820 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -