Submission #202118

#	Time	Username	Problem	Language	Result	Execution time	Memory
202118		shibh308	Examination (JOI19_examination)	C++17	2 / 100	3101 ms	177632 KiB

examination

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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;
    vector<int> elm;
    MiniSegtree(int n = 1) : n(n), elm(n + 1, 0){
    }
    void add(int x){
        for(++x; x <= n; x += x & -x)
            ++elm[x];
    }
    int get(int r){
        int res = 0;
        for(; r > 0; r -= r & -r)
            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(n), elements(n + 1), elm_inv(n + 1), seg(n + 1){
    }
    void set_val(int x, int y){
        for(++x; x <= n; x += x & -x)
            elements[x].emplace_back(y);
    }
    void build(){
        for(int i = 0; i <= 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; x <= n; x += x & -x)
            seg[x].add(elm_inv[x][y]);
    }
    int get_sum(int r, int y){
        int res = 0;
        for(; r > 0; r -= r & -r)
            res += seg[r].get(elm_inv[r].lower_bound(y)->second);
        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:41:26: warning: 'Segtree::elm_inv' will be initialized after [-Wreorder]
     vector<map<int,int>> elm_inv;
                          ^~~~~~~
examination.cpp:40:25: warning:   'std::vector<MiniSegtree> Segtree::seg' [-Wreorder]
     vector<MiniSegtree> seg;
                         ^~~
examination.cpp:42:5: warning:   when initialized here [-Wreorder]
     Segtree(int n) : n(n), elements(n + 1), elm_inv(n + 1), seg(n + 1){
     ^~~~~~~
examination.cpp: In member function 'void Segtree::build()':
examination.cpp:52: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:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < data.size(); ++i)
                    ~~^~~~~~~~~~~~~
examination.cpp:99: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