Submission #684715

#	Time	Username	Problem	Language	Result	Execution time	Memory
684715		esomer	Examination (JOI19_examination)	C++17	100 / 100	435 ms	31372 KiB

examination

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"
//~ #define int long long
 
typedef long long int ll;

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 segTree {
    int size;
    vector<ll> sums;
    void init(int n){
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, 0LL);
    }
    void set(int i, int v, int x, int lx, int rx){
        if (rx - lx == 1){
            sums[x] += v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m){
            set(i, v, 2 * x + 1, lx, m);
        }else{
            set(i, v, 2 * x + 2, m, rx);
        }
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
    }
    void set(int i, int v){
        set (i, v, 0, 0, size);
    }

    ll sum(int l, int r, int x, int lx, int rx){
        if (lx >= r || l >= rx){
            return 0;
        }
        if (lx >= l && rx <= r){
            return sums[x];
        }
        int m = (lx + rx) / 2;
        ll s1 = sum(l, r, 2 * x + 1, lx, m);
        ll s2 = sum(l, r, 2 * x + 2, m, rx);
        return s1 + s2;
    }

    ll sum (int l, int r){
        return sum(l, r, 0, 0, size);
    }
};


void solve(){
	int n, q; cin >> n >> q;
	vector<pair<int, int>> v(n);
	set<int> sa;
	set<int> 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;
	map<int, int> b;
	int curr = 1;
	for(auto x : sa){
		a[x] = curr;
		curr++;
	}
	segTree sta; sta.init(curr);
	int sza = curr;
	curr = 1;
	for(auto x : sb){
		b[x] = curr;
		curr++;
	}
	segTree 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.set(a[v[curr].first], 1);
			stb.set(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 << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

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