Submission #548310

#	Time	Username	Problem	Language	Result	Execution time	Memory
548310		Jomnoi	Examination (JOI19_examination)	C++17	2 / 100	3076 ms	21160 KiB

examination

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 1e5 + 10;
const int MAX_Q = 1e5 + 10;
const int B = 330;

int S[MAX_N], T[MAX_N], ST[MAX_N];
int X[MAX_Q], Y[MAX_Q], Z[MAX_Q];
int ans[MAX_Q];
vector <int> pA[2 * MAX_N], pB[2 * MAX_N];

class FenwickTree {
private :
    int N;
    vector <int> fenwick;
public :
    FenwickTree() {}
    FenwickTree(const int &n) : N(n), fenwick(N + 1, 0) {}

    void update(const int &idx, const int &val) {
        for(int i = idx; i <= N; i += (i & -i)) {
            fenwick[i] += val;
        }
    }

    int get(const int &idx) {
        int res = 0;
        for(int i = idx; i >= 1; i -= (i & -i)) {
            res += fenwick[i];
        }
        return res;
    }

    int query(const int &idx) {
        return get(N) - get(idx - 1);
    }
};

class Query {
public :
    int a, b, c, i;
    Query() {}
    Query(const int &a_, const int &b_, const int &c_, const int &i_) : a(a_), b(b_), c(c_), i(i_) {}

    bool operator<(const Query &o) const {
        return make_pair((a + B - 1) / B, b) < make_pair((o.a + B - 1) / B, o.b);
    }
};

void compress(vector <int> &vec) {
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;
    vector <int> sa({-1}), sb({-1}), sc({-1});
    for(int i = 1; i <= N; i++) {
        cin >> S[i] >> T[i];
        ST[i] = S[i] + T[i];
        sa.push_back(S[i]);
        sb.push_back(T[i]);
        sc.push_back(ST[i]);
    }
    for(int i = 1; i <= Q; i++) {
        cin >> X[i] >> Y[i] >> Z[i];
        sa.push_back(X[i]);
        sb.push_back(Y[i]);
        sc.push_back(Z[i]);
    }

    // Compress
    compress(sa);
    compress(sb);
    compress(sc);
    for(int i = 1; i <= N; i++) {
        S[i] = lower_bound(sa.begin(), sa.end(), S[i]) - sa.begin();
        T[i] = lower_bound(sb.begin(), sb.end(), T[i]) - sb.begin();
        ST[i] = lower_bound(sc.begin(), sc.end(), ST[i]) - sc.begin();

        pA[S[i]].push_back(i);
        pB[T[i]].push_back(i);
    }
    for(int i = 1; i < sa.size(); i++) {
        sort(pA[i].begin(), pA[i].end(), [&](const int &x, const int &y) {
            return T[x] > T[y];
        });
    }
    for(int i = 1; i < sb.size(); i++) {
        sort(pB[i].begin(), pB[i].end(), [&](const int &x, const int &y) {
            return S[x] > S[y];
        });
    }
    for(int i = 1; i <= Q; i++) {
        X[i] = lower_bound(sa.begin(), sa.end(), X[i]) - sa.begin();
        Y[i] = lower_bound(sb.begin(), sb.end(), Y[i]) - sb.begin();
        Z[i] = lower_bound(sc.begin(), sc.end(), Z[i]) - sc.begin();
    }

    // MO's algorithm
    vector <Query> query;
    for(int i = 1; i <= Q; i++) {
        query.push_back(Query(X[i], Y[i], Z[i], i));
    }
    sort(query.begin(), query.end());

    FenwickTree fw(sc.size());
    int cur_l, cur_r;
    for(int i = 0; i < Q; i++) {
        auto [l, r, c, id] = query[i];
        if(i == 0) {
            cur_l = l, cur_r = r;
            for(int i = 1; i <= N; i++) {
                if(S[i] >= cur_l and T[i] >= cur_r) {
                    fw.update(ST[i], 1);
                }
            }
        }
        else {
            while(cur_l > l) {
                cur_l--;
                for(auto idx : pA[cur_l]) {
                    if(T[idx] >= cur_r) {
                        fw.update(ST[idx], 1);
                    }
                    else {
                        break;
                    }
                }
            }
            while(cur_r < r) {
                for(auto idx : pB[cur_r]) {
                    if(S[idx] >= cur_l) {
                        fw.update(ST[idx], -1);
                    }
                    else {
                        break;
                    }
                }
                cur_r++;
            }
            while(cur_l < l) {
                for(auto idx : pA[cur_l]) {
                    if(T[idx] >= cur_r) {
                        fw.update(ST[idx], -1);
                    }
                    else {
                        break;
                    }
                }
                cur_l++;
            }
            while(cur_r > r) {
                cur_r--;
                for(auto idx : pB[cur_r]) {
                    if(S[idx] >= cur_l) {
                        fw.update(ST[idx], 1);
                    }
                    else {
                        break;
                    }
                }
            }
        }

        ans[id] = fw.query(c);
    }

    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 1; i < sa.size(); i++) {
      |                    ~~^~~~~~~~~~~
examination.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 1; i < sb.size(); i++) {
      |                    ~~^~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57