Submission #158411

#	Time	Username	Problem	Language	Result	Execution time	Memory
158411		jhwest2	Examination (JOI19_examination)	C++14	20 / 100	299 ms	13220 KiB

examination

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct Tup { int x, y, c, i; };

const int MAX = 1e5+1;
int N, Q;
int ans[MAX];
Tup A[MAX], B[MAX];
vector<int> v;

struct PEN {
	int tree[8*MAX];

	void update(int x) { for(; x<8*MAX; x+=x&-x) ++tree[x]; }
	int query(int a, int b) {
		int ret = 0; --a;
		for (; b; b-=b&-b) ret += tree[b];
		for (; a; a-=a&-a) ret -= tree[a];
		return ret;
	}
} seg;

void compress() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i=0; i<N; i++) {
		A[i].x = lower_bound(v.begin(), v.end(), A[i].x)-v.begin()+1;
		A[i].y = lower_bound(v.begin(), v.end(), A[i].y)-v.begin()+1;
	}
	for (int i=0; i<Q; i++) {
		B[i].x = lower_bound(v.begin(), v.end(), B[i].x)-v.begin()+1;
		B[i].y = lower_bound(v.begin(), v.end(), B[i].y)-v.begin()+1;
		B[i].c = lower_bound(v.begin(), v.end(), B[i].c)-v.begin()+1;
	}
}
bool cmp1(Tup &a, Tup &b) { return a.x<b.x; }
bool cmp2(Tup &a, Tup &b) { return a.x+a.y<b.x+b.y; }

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

	cin >> N >> Q;
	for (int i=0; i<N; i++) {
		cin >> A[i].x >> A[i].y;
		v.push_back(A[i].x); v.push_back(A[i].y);
		v.push_back(A[i].x+A[i].y);
	}
	for (int i=0; i<Q; i++) {
		cin >> B[i].x >> B[i].y >> B[i].c; B[i].i = i;
		v.push_back(B[i].x); v.push_back(B[i].y);
		v.push_back(B[i].x+B[i].y); v.push_back(B[i].c);
		if (B[i].c > B[i].x) v.push_back(B[i].c-B[i].x);
	}
	compress();

	sort(A, A+N, cmp1); sort(B, B+Q, cmp1);

	int ap=-1, bp=-1;
	for (int i=0; i<v.size(); i++) {
		while (bp+1 < Q && B[bp+1].x == i+1) {
			++bp;
			ans[B[bp].i] -= seg.query(B[bp].y, 8*MAX-1);
			if (v[B[bp].x-1] + v[B[bp].y-1] < v[B[bp].c-1]) {
				int idx = lower_bound(v.begin(), v.end(), v[B[bp].c-1]-v[B[bp].x-1]) - v.begin()+1;
				ans[B[bp].i] += seg.query(B[bp].y, idx);
			}
		}
		while (ap+1 < N && A[ap+1].x == i+1) {
			seg.update(A[ap+1].y); ++ap;
		}
	}
	for (int i=0; i<Q; i++) ans[B[i].i] += seg.query(B[i].y, 8*MAX-1);

	sort(A, A+N, cmp2); sort(B, B+Q, cmp2);
	for (int i=1; i<7*MAX; i++) seg.tree[i] = 0;

	ap = -1; bp = -1;
	for (int i=0; i<v.size(); i++) {
		while (bp+1 < Q && B[bp+1].c == i+1) {
			++bp;
			if (v[B[bp].c-1] > v[B[bp].x-1] + v[B[bp].y-1]) {
				int idx = lower_bound(v.begin(), v.end(), v[B[bp].c-1]-v[B[bp].x-1]) - v.begin()+1;
				ans[B[bp].i] -= seg.query(B[bp].y, idx);
			}
		}

		while (ap+1 < N && v[A[ap+1].x-1] + v[A[ap+1].y-1] == v[i]) {
			seg.update(A[ap+1].y); ++ap;
		}
	}

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

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~
examination.cpp:84:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~

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