oj.uz

Submission #202115

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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 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 71 ms 10332 KB Output is correct
8 Correct 68 ms 10332 KB Output is correct
9 Correct 72 ms 10328 KB Output is correct
10 Correct 60 ms 10328 KB Output is correct
11 Correct 68 ms 10304 KB Output is correct
12 Correct 64 ms 10200 KB Output is correct
13 Correct 65 ms 10328 KB Output is correct
14 Correct 65 ms 10320 KB Output is correct
15 Correct 72 ms 10328 KB Output is correct
16 Correct 66 ms 10200 KB Output is correct
17 Correct 70 ms 10328 KB Output is correct
18 Correct 51 ms 10200 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 394512 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 3060 ms 394512 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 6 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 71 ms 10332 KB Output is correct
8 Correct 68 ms 10332 KB Output is correct
9 Correct 72 ms 10328 KB Output is correct
10 Correct 60 ms 10328 KB Output is correct
11 Correct 68 ms 10304 KB Output is correct
12 Correct 64 ms 10200 KB Output is correct
13 Correct 65 ms 10328 KB Output is correct
14 Correct 65 ms 10320 KB Output is correct
15 Correct 72 ms 10328 KB Output is correct
16 Correct 66 ms 10200 KB Output is correct
17 Correct 70 ms 10328 KB Output is correct
18 Correct 51 ms 10200 KB Output is correct
19 Execution timed out 3060 ms 394512 KB Time limit exceeded
20 Halted 0 ms 0 KB -