oj.uz

Submission #158412

# Submission time Handle Problem Language Result Execution time Memory
158412 2019-10-17T01:41:57 Z jhwest2 Examination (JOI19_examination) C++14
20 / 100
 307 ms 10288 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, [&](Tup a, Tup b) { return a.c < b.c;});
	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 237 ms 9992 KB Output is correct
2 Correct 238 ms 10080 KB Output is correct
3 Correct 238 ms 9992 KB Output is correct
4 Correct 190 ms 10056 KB Output is correct
5 Correct 185 ms 10076 KB Output is correct
6 Correct 130 ms 10044 KB Output is correct
7 Correct 230 ms 10080 KB Output is correct
8 Correct 231 ms 10112 KB Output is correct
9 Correct 220 ms 10152 KB Output is correct
10 Correct 175 ms 9960 KB Output is correct
11 Correct 189 ms 9824 KB Output is correct
12 Correct 110 ms 9700 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9992 KB Output is correct
2 Correct 238 ms 10080 KB Output is correct
3 Correct 238 ms 9992 KB Output is correct
4 Correct 190 ms 10056 KB Output is correct
5 Correct 185 ms 10076 KB Output is correct
6 Correct 130 ms 10044 KB Output is correct
7 Correct 230 ms 10080 KB Output is correct
8 Correct 231 ms 10112 KB Output is correct
9 Correct 220 ms 10152 KB Output is correct
10 Correct 175 ms 9960 KB Output is correct
11 Correct 189 ms 9824 KB Output is correct
12 Correct 110 ms 9700 KB Output is correct
13 Incorrect 307 ms 10288 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 -