Submission #685291

#	Time	Username	Problem	Language	Result	Execution time	Memory
685291		izanbf	Examination (JOI19_examination)	C++14	100 / 100	407 ms	23384 KiB

examination

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int MOD = 1e9 + 7;
const int maxN = 200000;
 
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first + a.second > b.first + b.second;
}
 
bool cmp2(tuple<int, int, int, int> a, tuple<int, int, int, int> b){
    return get<2>(a) > get<2>(b);
}
 
struct BIT {
    int* bit;
    int n;
 
    void init(int n_) {
        n = n_+1;
        bit = new int[n+1];
        fill(bit, bit+n+1, 0);
    }

    int sum(int r) {
        int sum = 0;
        for (; r > 0; r -= r&-r)
            sum += bit[r];
        return sum;
    }

    int sum(int l, int r) { return sum(r) - sum(l-1); }
     
    void add(int r, int delta) {
        for (++r; r <= n; r += r&-r)
            bit[r] += delta;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, q; cin >> n >> q;
    vector<pair<int, int>> v(n);
    set<int> sa, sb;
    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y;
        v[i] = {x, y};
        sa.insert(x);
        sb.insert(y);
    }
    map<int, int> a, b;
    int curr = 1;
    for(auto x : sa){
        a[x] = curr;
        curr++;
    }
    BIT sta; sta.init(curr);
    int sza = curr;
    curr = 1;
    for(auto x : sb){
        b[x] = curr;
        curr++;
    }
    BIT stb; stb.init(curr);
    int szb = curr;
    sort(v.begin(), v.end(), cmp);
    vector<tuple<int, int, int, int>> queries(q);
    for(int i = 0; i < q; i++){
        int x, y, z; cin >> x >> y >> z;
        int nx = sza;
        auto it = a.lower_bound(x);
        if(it != a.end()) nx = (*it).second;
        int ny = szb;
        it = b.lower_bound(y);
        if(it != b.end()) ny = (*it).second;
        queries[i] = {nx, ny, max(z, x + y), i};
    }
    sort(queries.begin(), queries.end(), cmp2);
    vector<int> ans(q);
    curr = 0;
    for(int i = 0; i < q; i++){
        while(curr < n && v[curr].first + v[curr].second >= get<2>(queries[i])){
            sta.add(a[v[curr].first], 1);
            stb.add(b[v[curr].second], 1);
            curr++;
        }
        int total = curr - sta.sum(1, get<0>(queries[i])) - stb.sum(1, get<1>(queries[i]));
        ans[get<3>(queries[i])] = total;
    }
    for(int x : ans) cout << x << '\n';
}

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