Submission #1296914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296914		harryleee	Examination (JOI19_examination)	C++20	100 / 100	1078 ms	308256 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, q, ans[maxn];
pair<int, int> a[maxn], b[maxn];
struct g{
    int x, y, z, id;
} query[maxn];
vector<int> nen1, nen2;

inline void input(){
    cin >> n >> q;
    for (int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second;
        nen1.push_back(a[i].first);
        nen2.push_back(a[i].second);
    }
    for (int i = 0; i < q; ++i){
        cin >> query[i].x >> query[i].y >> query[i].z;
        query[i].id = i;
    }
    
    return;
}

inline void compute(){
    sort(nen1.begin(), nen1.end()); sort(nen2.begin(), nen2.end());
    nen1.erase(unique(nen1.begin(), nen1.end()), nen1.end());
    nen2.erase(unique(nen2.begin(), nen2.end()), nen2.end());

    sort(a, a + n, [](const pair<int, int>& u, const pair<int, int>& v){
        return u.first + u.second < v.first + v.second;
    });
    sort(query, query + q, [](const g& u, const g& v){
        return u.z < v.z;
    });

    for (int i = 0; i < n; ++i){
        b[i].first = lower_bound(nen1.begin(), nen1.end(), a[i].first) - nen1.begin();
        b[i].second = lower_bound(nen2.begin(), nen2.end(), a[i].second) - nen2.begin();
        // exist[b[i].first]++;
    }
    return;
}

struct trie{
    struct NODE{
        int nxt[2], cnt;
        inline NODE(){
            nxt[0] = nxt[1] = -1;
            cnt = 0;
        }
    }; vector<NODE> node;
    inline trie(){
        node.push_back(NODE());
    }
    inline void insert(int val){
        int pos = 0;
        for (int i = 16; i >= 0; --i){
            int bit = (val >> i) & 1;
            if (node[pos].nxt[bit] == -1){
                node[pos].nxt[bit] = (int)node.size();
                node.push_back(NODE());
            }
            pos = node[pos].nxt[bit];
            node[pos].cnt++;
        }
        return;
    }
    inline int get(int val){
        int pos = 0, res = 0;
        for (int i = 16; i >= 0; --i){
            int bit = (val >> i) & 1;
            if (bit == 0 && node[pos].nxt[1] != -1){
                res += node[node[pos].nxt[1]].cnt;
            }
            if (node[pos].nxt[bit] == -1) return res;
            pos = node[pos].nxt[bit];
        }
        return res + node[pos].cnt;
    }
};


struct SEGMENT_TREE{
    vector<trie> st;
    inline SEGMENT_TREE(int n){
        st.resize(4 * n);
    }
    inline void update(int ind, int l, int r, int pos, int val){
        st[ind].insert(val);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (mid >= pos) update(ind << 1, l, mid, pos, val);
        else update(ind << 1 | 1, mid + 1, r, pos, val);
        return;
    }
    inline int get(int ind, int l, int r, int lb, int rb, int val){
        if (l >= lb && r <= rb) return st[ind].get(val);
        int mid = (l + r) >> 1, ans = 0;
        if (mid >= lb) ans += get(ind << 1, l, mid, lb, rb, val);
        if (mid < rb) ans += get(ind << 1 | 1, mid + 1, r, lb, rb, val);
        return ans;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    compute();

    SEGMENT_TREE seg(nen1.size());

    // for (int x : nen1) cout << x << ' ';
    // cout << endl;
    // for (int x : nen2) cout << x << " ";
    // cout << endl;
    // for (int i = 0; i < q; ++i) cout << query[i].x << ' ' << query[i].y << ' ' << query[i].z << '\n';
    
    for (int i = q - 1, j = n - 1; i >= 0; --i){
        while(j >= 0 && a[j].first + a[j].second >= query[i].z){
            seg.update(1, 0, nen1.size() - 1, b[j].first, b[j].second);
            j--;
        }
        int it1 = lower_bound(nen1.begin(), nen1.end(), query[i].x) - nen1.begin();
        int it2 = lower_bound(nen2.begin(), nen2.end(), query[i].y) - nen2.begin();
        // cout << it1 << ' ' << it2 << '\n';
        if (it1 != nen1.size() && it2 != nen2.size())
            ans[query[i].id] = seg.get(1, 0, nen1.size() - 1, it1, nen1.size() - 1, it2);
    }

    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

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