oj.uz

Submission #202118

# Submission time Handle Problem Language Result Execution time Memory
202118 2020-02-14T00:42:42 Z shibh308 Examination (JOI19_examination) C++17
2 / 100
 3000 ms 177632 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 42 ms 4952 KB Output is correct
8 Correct 44 ms 4824 KB Output is correct
9 Correct 43 ms 4824 KB Output is correct
10 Correct 43 ms 4824 KB Output is correct
11 Correct 43 ms 4824 KB Output is correct
12 Correct 36 ms 4824 KB Output is correct
13 Correct 41 ms 4824 KB Output is correct
14 Correct 44 ms 4824 KB Output is correct
15 Correct 41 ms 4824 KB Output is correct
16 Correct 36 ms 4828 KB Output is correct
17 Correct 42 ms 4824 KB Output is correct
18 Correct 31 ms 4824 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3101 ms 177632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3101 ms 177632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 42 ms 4952 KB Output is correct
8 Correct 44 ms 4824 KB Output is correct
9 Correct 43 ms 4824 KB Output is correct
10 Correct 43 ms 4824 KB Output is correct
11 Correct 43 ms 4824 KB Output is correct
12 Correct 36 ms 4824 KB Output is correct
13 Correct 41 ms 4824 KB Output is correct
14 Correct 44 ms 4824 KB Output is correct
15 Correct 41 ms 4824 KB Output is correct
16 Correct 36 ms 4828 KB Output is correct
17 Correct 42 ms 4824 KB Output is correct
18 Correct 31 ms 4824 KB Output is correct
19 Execution timed out 3101 ms 177632 KB Time limit exceeded
20 Halted 0 ms 0 KB -