Submission #383930

#	Time	Username	Problem	Language	Result	Execution time	Memory
383930		nikatamliani	Examination (JOI19_examination)	C++14	100 / 100	249 ms	23020 KiB

examination

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
template <typename T>
struct fenwick_tree {
    int size;
    vector<T> tree;
    T neutral;
    fenwick_tree(int n, T _neutral) {
        size = n;
        neutral = _neutral;
        tree = vector<T>(n + 1);
    }
 
    void update(int index, T value) {
        for(; index <= size; index += index & -index) {
            tree[index] += value;
        }
    }
    T query_prefix(int index) {
        T ans = neutral;
        for(; index; index -= index & -index) {
            ans += tree[index];
        }
        return ans; 
    }
    T query(int l, int r) {
        return query_prefix(r) - query_prefix(l - 1);
    }
};
map<int, int> compress(vector<int> &coords) {
	sort(coords.begin(), coords.end());
	map<int, int> compressed;
	for(int i = 0, current = 0; i < (int)coords.size(); ++i) {
		if(i == 0 || coords[i] != coords[i - 1]) ++current;
		compressed[coords[i]] = current;
	}
	return compressed;
}
struct point {
	int x, y, sum;
	bool operator < (const point &other) {
		if(x == other.x) {
			return y < other.y;
		}
		return x < other.x;
	}
};
point a[N], b[N];
void compress(vector<int*> &coords) {
	sort(coords.begin(), coords.end(), [&](const int* x, const int* y) {
		return *x < *y;
	});
	int prev = -1;
	for(int i = 0, current = 0; i < (int)coords.size(); ++i) {
		if(prev != *coords[i]) {
			++current;
		}
		prev = *coords[i];
		*coords[i] = current;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m; 
	vector<vector<int>> v;
	vector<int> sorted_sums;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].y;
		a[i].sum = a[i].x + a[i].y;
		sorted_sums.push_back(a[i].sum);
	}
	sort(sorted_sums.begin(), sorted_sums.end());
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= m; ++i) {
		cin >> b[i].x >> b[i].y >> b[i].sum;
		b[i].sum = max(b[i].sum, b[i].x + b[i].y);
	}
	vector<int> ans(m+1);
	for(int i = 1; i <= m; ++i) {
		int l = 0, r = n - 1, ind = n;
		while(r >= l) {
			int middle = l + r >> 1;
			if(sorted_sums[middle] >= b[i].sum) {
				r = middle - 1;
				ind = middle;
			} else {
				l = middle + 1;
			}
		}
		ans[i] = n - ind;
	}
	vector<int*> coords(n+m);
	for(int i = 0; i < n + m; ++i) {
		coords[i] = i < n ? &a[i + 1].x : &b[i + 1 - n].x;
	}
	compress(coords);
	for(int i = 0; i < n + m; ++i) {
		coords[i] = i < n ? &a[i + 1].y : &b[i + 1 - n].y;
	}
	compress(coords);
	for(int i = 0; i < n + m; ++i) {
		coords[i] = i < n ? &a[i + 1].sum : &b[i + 1 - n].sum;
	}
	compress(coords);
	fenwick_tree<int> tx(2 * N, 0);
	fenwick_tree<int> ty(2 * N, 0);
	vector<int> sums[2 * N], queries[2 * N];
	for(int i = 1; i <= n; ++i) {
		int val = a[i].sum;
		sums[val].push_back(i); 
	}
	for(int i = 1; i <= m; ++i) {
		int val = b[i].sum;
		queries[val].push_back(i);
	}
	for(int i = 2 * N - 1; i >= 1; --i) {
		for(int id : sums[i]) {
			int val_x = a[id].x;
			int val_y = a[id].y;
			tx.update(val_x, 1); 
			ty.update(val_y, 1);
		}
		for(int id : queries[i]) {
			int val_x = b[id].x;
			int val_y = b[id].y;
			ans[id] -= tx.query_prefix(val_x - 1);
			ans[id] -= ty.query_prefix(val_y - 1);
		}
	}
	for(int i = 1; i <= m; ++i) {
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |    int middle = l + r >> 1;
      |                 ~~^~~

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