Submission #1120405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120405		Thunnus	Examination (JOI19_examination)	C++17	100 / 100	388 ms	41388 KiB

examination

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
 
const int MAX = 1e5 + 5;
 
struct Item{
    int x, y, z, i, t;
    Item(int x, int y, int z, int i, int t) : x(x), y(y), z(z), i(i), t(t) {}
};
vector<Item> queries;
 
struct BIT{
    vi bit;
    BIT(int n) : bit(n + 1) {}
 
    inline void add(int idx, int val){
        for(++idx; idx < sz(bit); idx += idx & -idx){
            bit[idx] += val;
        }
        return;
    }
 
    inline int query(int idx){
        int ret = 0;
        for(++idx; idx; idx -= idx & -idx){
            ret += bit[idx];
        }
        return ret;
    }
};
 
vi ans(MAX);
BIT bit(6 * MAX);
inline void cdq(int l, int r){
    if(l + 1 == r) return;
    int m = (l + r) / 2;
    cdq(l, m); cdq(m, r);
    vector<Item> temp;
    vi er;
    int a = l, b = m, num = 0;
    while(a < m && b < r){
        if(queries[a].y >= queries[b].y){
			if(!queries[a].t){
				bit.add(queries[a].z, 1);
				er.emplace_back(queries[a].z);
				num++;
			}
            temp.emplace_back(queries[a++]);
        }
        else{
            if(queries[b].t){
                ans[queries[b].i] += num - bit.query(queries[b].z - 1);
            }
            temp.emplace_back(queries[b++]);
        }
    }
    while(a < m){
        temp.emplace_back(queries[a++]);
    }
    while(b < r){
        if(queries[b].t){
			ans[queries[b].i] += num - bit.query(queries[b].z - 1);
		}
		temp.emplace_back(queries[b++]);
    }
    for(int i = l; i < r; i++){
        queries[i] = temp[i - l];
    }
    for(int &i : er){
        bit.add(i, -1);
    }
    temp.clear(), er.clear();
    return;
}
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q, x, y, z;
    cin >> n >> q;
    vi c;
    for(int i = 0; i < n + q; i++){
        cin >> x >> y;
        if(i >= n){
            cin >> z;
        }
        else{
            z = x + y;
        }
        queries.emplace_back(x, y, z, i - n, i >= n);
        c.emplace_back(x), c.emplace_back(y), c.emplace_back(z);
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
 
    auto compress = [&](int val) -> int {
        return lower_bound(c.begin(), c.end(), val) - c.begin();
    };
 
    for(int i = 0; i < n + q; i++){
        queries[i].x = compress(queries[i].x);
        queries[i].y = compress(queries[i].y);
        queries[i].z = compress(queries[i].z);
    }
    sort(queries.begin(), queries.end(), [&](const Item &a, const Item &b){return a.x == b.x ? (a.y == b.y ? (a.z == b.z ? a.t < b.t : a.z > b.z) : a.y > b.y) : a.x > b.x;} );
    cdq(0, n + q);
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    cout << "\n";
    return 0;
}

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