Submission #722481

#	Time	Username	Problem	Language	Result	Execution time	Memory
722481		saayan007	Examination (JOI19_examination)	C++17	20 / 100	98 ms	10820 KiB

examination

#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
• Subtask 2: 20 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57