Submission #202115

#	Time	Username	Problem	Language	Result	Execution time	Memory
202115		shibh308	Examination (JOI19_examination)	C++17	2 / 100	3060 ms	394512 KiB

examination

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

const i64 MOD = i64(1e9) + 7;
const i64 INF = i64(1e18) + 7;


struct Data{
    Data(int x, int y, int z, int idx, bool student) : x(x), y(y), z(z), idx(idx), student(student){}
    int x, y, z, idx;
    bool student;
};

struct MiniSegtree{
    int n, cnt;
    vector<int> elm;
    MiniSegtree(int n_ = 2) : n(1 << (32 - __builtin_clz(n_ - 1))), cnt(0), elm(2 * n, 0){
    }
    void add(int x){
        ++cnt;
        for(x += n; x; x >>= 1)
            ++elm[x];
    }
    int get(int l){
        int res = 0;
        l += n;
        for(int r = 2 * n - 1; l <= r; l >>= 1, r >>= 1){
            if(l & 1)
                res += elm[l++];
            if(!(r & 1))
                res += elm[r--];
        }
        return res;
    }
};

struct Segtree{
    int n;
    vector<vector<int>> elements;
    vector<MiniSegtree> seg;
    vector<map<int,int>> elm_inv;
    Segtree(int n_) : n(1 << (32 - __builtin_clz(n_ - 1))), elements(2 * n), elm_inv(2 * n), seg(2 * n){
    }
    void set_val(int x, int y){
        for(x += n; x; x >>= 1)
            elements[x].emplace_back(y);
    }
    void build(){
        for(int i = 1; i < 2 * n; ++i){
            sort(elements[i].begin(), elements[i].end());
            elements[i].push_back(MOD);
            for(int j = 0; j < elements[i].size(); ++j)
                elm_inv[i][elements[i][j]] = j;
            seg[i] = MiniSegtree(elements[i].size());
        }
    }
    void add(int x, int y){
        for(x += n; x; x >>= 1){
            seg[x].add(elm_inv[x][y]);
        }
    }
    int get_sum(int l, int y){
        int res = 0;
        l += n;
        for(int r = 2 * n - 1; l <= r; l >>= 1, r >>= 1){
            if(l & 1){
                // res += seg[l].get(elm_inv[l][y]);
                res += seg[l].get(elm_inv[l].lower_bound(y)->second);
                l++;
            }
            if(!(r & 1)){
                assert(elm_inv[r].find(y) != elm_inv[r].end());
                // res += seg[r].get(elm_inv[r][y]);
                res += seg[r].get(elm_inv[r].lower_bound(y)->second);
                r--;
            }
        }
        return res;
    }

};


signed main(){

    int n, q;
    cin >> n >> q;
    vector<int> s(n), t(n);

    for(int i = 0; i < n; ++i)
        cin >> s[i] >> t[i];


    vector<Data> data;

    for(int i = 0; i < q; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        data.emplace_back(x, y, z, i, false);
    }

    for(int i = 0; i < n; ++i)
        data.emplace_back(s[i], t[i], s[i] + t[i], i, true);

    map<pair<bool, int>, int> x_idxes, y_idxes;

    sort(data.begin(), data.end(), [](const auto& a, const auto& b){return a.x == b.x ? a.student < b.student : a.x < b.x;});
    for(int i = 0; i < data.size(); ++i)
        x_idxes[make_pair(data[i].student, data[i].idx)] = i;

    sort(data.begin(), data.end(), [](const auto& a, const auto& b){return a.y == b.y ? a.student < b.student : a.y < b.y;});
    for(int i = 0; i < data.size(); ++i)
        y_idxes[make_pair(data[i].student, data[i].idx)] = i;

    Segtree seg(n + q);

    for(auto& d : data){
        int x_idx = x_idxes[make_pair(d.student, d.idx)];
        int y_idx = y_idxes[make_pair(d.student, d.idx)];
        seg.set_val(x_idx, y_idx);
    }

    sort(data.begin(), data.end(), [](const auto& a, const auto& b){return a.z == b.z ? a.student > b.student : a.z > b.z;});

    seg.build();

    vector<int> ans(q, -1);
    for(auto& d : data){
        int x_idx = x_idxes[make_pair(d.student, d.idx)];
        int y_idx = y_idxes[make_pair(d.student, d.idx)];
        if(d.student){
            seg.add(x_idx, y_idx);
        }
        else{
            ans[d.idx] = seg.get_sum(x_idx, y_idx);
        }
    }
    for(int i = 0; i < q; ++i)
        cout << ans[i] << endl;
}

Compilation message (stderr)

examination.cpp: In constructor 'Segtree::Segtree(int)':
examination.cpp:44:26: warning: 'Segtree::elm_inv' will be initialized after [-Wreorder]
     vector<map<int,int>> elm_inv;
                          ^~~~~~~
examination.cpp:43:25: warning:   'std::vector<MiniSegtree> Segtree::seg' [-Wreorder]
     vector<MiniSegtree> seg;
                         ^~~
examination.cpp:45:5: warning:   when initialized here [-Wreorder]
     Segtree(int n_) : n(1 << (32 - __builtin_clz(n_ - 1))), elements(2 * n), elm_inv(2 * n), seg(2 * n){
     ^~~~~~~
examination.cpp: In member function 'void Segtree::build()':
examination.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < elements[i].size(); ++j)
                            ~~^~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < data.size(); ++i)
                    ~~^~~~~~~~~~~~~
examination.cpp:115:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < data.size(); ++i)
                    ~~^~~~~~~~~~~~~

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