oj.uz

Submission #158411

# Submission time Handle Problem Language Result Execution time Memory
158411 2019-10-17T01:29:45 Z jhwest2 Examination (JOI19_examination) C++14
20 / 100
 299 ms 13220 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 12552 KB Output is correct
2 Correct 249 ms 12640 KB Output is correct
3 Correct 247 ms 12612 KB Output is correct
4 Correct 195 ms 11808 KB Output is correct
5 Correct 194 ms 11844 KB Output is correct
6 Correct 134 ms 11100 KB Output is correct
7 Correct 243 ms 12424 KB Output is correct
8 Correct 241 ms 12512 KB Output is correct
9 Correct 229 ms 12384 KB Output is correct
10 Correct 185 ms 11632 KB Output is correct
11 Correct 195 ms 11620 KB Output is correct
12 Correct 112 ms 10712 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 12552 KB Output is correct
2 Correct 249 ms 12640 KB Output is correct
3 Correct 247 ms 12612 KB Output is correct
4 Correct 195 ms 11808 KB Output is correct
5 Correct 194 ms 11844 KB Output is correct
6 Correct 134 ms 11100 KB Output is correct
7 Correct 243 ms 12424 KB Output is correct
8 Correct 241 ms 12512 KB Output is correct
9 Correct 229 ms 12384 KB Output is correct
10 Correct 185 ms 11632 KB Output is correct
11 Correct 195 ms 11620 KB Output is correct
12 Correct 112 ms 10712 KB Output is correct
13 Incorrect 299 ms 13220 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -