oj.uz

Submission #875306

# Submission time Handle Problem Language Result Execution time Memory
875306 2023-11-19T04:30:19 Z atom Examination (JOI19_examination) C++17
0 / 100
 545 ms 32420 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#define fi first
#define se second
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

#define int long long

using pii = pair < int, int >;
const int INF = 2e9;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;

struct Fenwick {
    int n;
    vector <int> f;
    void init (int _n) {
        n = _n;
        f.resize(_n + 5);
    }
    int get(int x) {
        int ans = 0;
        for (; x; x -= x & -x)
            ans += f[x];
        return ans;
    }
    void upd(int x, int val) {
        for (; x <= n; x += x & -x)
            f[x] += val;
    } 
    int qry(int l) { return get(n) - get(l - 1); }
} fen;


int n, q;
int a[N], ans[N];
vector <vector <int>> queries;

void dnc(int l, int r) {
    if (l == r) return;

    int m = (l + r) / 2;
    dnc(l, m);
    dnc(m + 1, r);

    vector <vector <int>> qs;
    // Al < Am < Ar -> only take student in right to update 
    for (int i = m + 1; i <= r; ++i) {
        auto x = queries[i];
        if (x[3] == -1)
            qs.push_back({x[1], x[2], -1});
    }

    // Solving queries in the left
    for (int i = l; i <= m; ++i) {
        auto x = queries[i];
        if (x[3] != -1)
            qs.push_back({x[1], x[2], x[3]});
    }
    sort(qs.begin(), qs.end());
    reverse(qs.begin(), qs.end());
    // Sort by Informatics points
    for (auto& x : qs) {
        if (x[2] == -1)
            fen.upd(x[1], 1);
        else 
            ans[x[2]] += fen.qry(x[1]);
    }

    // Undoing changes
    for (auto& x : qs) {
        if (x[2] == -1)
            fen.upd(x[1], -1);
    }
}

void run_case() {
    cin >> n >> q;

    vector <int> val;
    val.push_back(INF);
    val.push_back(2 * INF);
    int Q = n + q;
    for (int i = 1; i <= n; ++i) {
        int s, t; 
        cin >> s >> t;
        queries.push_back({s, t, s + t, -1});
        val.push_back(s);
        val.push_back(t);
        val.push_back(s + t);
    }

    for (int i = 1; i <= q; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        queries.push_back({x, y, z, i});
        val.push_back(x);
        val.push_back(y);
        val.push_back(z);
    }

    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());

    int sz = val.size();
    fen.init(sz + 5);
    // sort by Maths points
    sort(queries.begin(), queries.end());

    // for (auto x : queries) {
    //     debug(x);
    // }

    for (auto& x : queries) {
        for (int i = 0; i < (int) x.size() - 1; ++i)
            x[i] = lower_bound(val.begin(), val.end(), x[i]) - val.begin() + 1; 
    }

    // for (auto x : queries) {
    //     debug(x);
    // }

    dnc(0, Q - 1);
    for (int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int Test = 1;
    //cin >> Test;
    for (int test = 1; test <= Test; test++){

        run_case();
    }
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 1308 KB Output is correct
8 Correct 11 ms 1308 KB Output is correct
9 Correct 11 ms 1304 KB Output is correct
10 Correct 10 ms 1304 KB Output is correct
11 Correct 9 ms 1308 KB Output is correct
12 Incorrect 7 ms 1116 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 31380 KB Output is correct
2 Correct 514 ms 31384 KB Output is correct
3 Correct 545 ms 32420 KB Output is correct
4 Correct 487 ms 31380 KB Output is correct
5 Correct 409 ms 30356 KB Output is correct
6 Incorrect 328 ms 31384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 31380 KB Output is correct
2 Correct 514 ms 31384 KB Output is correct
3 Correct 545 ms 32420 KB Output is correct
4 Correct 487 ms 31380 KB Output is correct
5 Correct 409 ms 30356 KB Output is correct
6 Incorrect 328 ms 31384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 1308 KB Output is correct
8 Correct 11 ms 1308 KB Output is correct
9 Correct 11 ms 1304 KB Output is correct
10 Correct 10 ms 1304 KB Output is correct
11 Correct 9 ms 1308 KB Output is correct
12 Incorrect 7 ms 1116 KB Output isn't correct
13 Halted 0 ms 0 KB -