Submission #715199

#	Time	Username	Problem	Language	Result	Execution time	Memory
715199		ismayil	Examination (JOI19_examination)	C++17	0 / 100	93 ms	18684 KiB

examination

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5 + 1;
struct segtree{
    vector<vector<int>> tree;
    int size;
    void init(int n){
        size = 1; 
        while(size < n) size *= 2;
        tree.resize(2 * n - 1);
    }   
    void build(vector<vector<int>> &a, int x, int lx, int rx){
        if(lx == rx){
            if(lx < a.size()) tree[x] = a[lx];
            return;
        }
        int mx = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, mx);
        build(a, 2 * x + 2, mx + 1, rx);
        merge(tree[2 * x + 1].begin(), tree[2 * x + 1].end(), tree[2 * x + 2].begin(), tree[2 * x + 2].end(), tree[x].begin());
    }
    void build(vector<vector<int>> &a){
        init(a.size());
        build(a, 0, 0, size - 1);
    }
    int query(int l, int r, int y, int x, int lx, int rx){
        if(r < lx || rx < l) return 0;
        if(l <= lx && rx <= r){
            return tree[x].size() - (lower_bound(tree[x].begin(), tree[x].end(), y) - tree[x].begin());
        }
        int mx = (lx + rx) / 2;
        return query(l, r, y, 2 * x + 1, lx, mx) + query(l, r, y, 2 * x + 2, mx + 1, rx);
    }
    int query(int l, int r, int y){
        return query(l, r, y, 0, 0, size - 1);
    }
};
int main(){
    int n, m;
    cin>>n>>m;
    vector<vector<int>> a(MAX);
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        a[x].push_back(y);
    }
    segtree st;
    st.build(a);
    for(int i = 0; i < m; i++){
        int x, y, z;
        cin>>x>>y>>z;
        cout<<st.query(x, MAX - 1, y)<<endl;
    }
}

Compilation message (stderr)

examination.cpp: In member function 'void segtree::build(std::vector<std::vector<int> >&, int, int, int)':
examination.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |             if(lx < a.size()) tree[x] = a[lx];
      |                ~~~^~~~~~~~~~

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