oj.uz

답안 #237225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237225 2020-06-05T09:53:38 Z DIvanCode Plahte (COCI17_plahte) C++14
0 / 160
 226 ms 11300 KB 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<ctime>
#include<cassert>
#include<complex>
#include<string>
#include<cstring>
#include<chrono>
#include<random>
#include<bitset>
#include<iomanip>

#define x first
#define y second
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define sz(v) (int) v.size()

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int MAX_N = 8e4 + 5;

int n, m;
pii a[MAX_N], b[MAX_N], c[MAX_N];
int cnt[MAX_N], tree[MAX_N * 12];

void update(int v, int tl, int tr, int pos, int delta) {
	if (tl + 1 == tr) {
		tree[v] += delta;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm) {
		update(v * 2 + 1, tl, tm, pos, delta);
	} else {
		update(v * 2 + 2, tm, tr, pos, delta);
	}
	tree[v] = tree[v * 2 + 1] + tree[v * 2 + 2];
}

int get_sum(int v, int tl, int tr, int L, int R) {
	if (tl >= R || L >= tr) {
		return 0;
	}
	if (L <= tl && tr <= R) {
		return tree[v];
	}
	int tm = (tl + tr) / 2;
	return get_sum(v * 2 + 1, tl, tm, L, R) + get_sum(v * 2 + 2, tm, tr, L, R);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	vector<pair<int, pii>> sc;
	vector<int> diff;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
		sc.eb(a[i].x, mp(-1, i));
		sc.eb(b[i].x, mp(1, i));
		diff.eb(a[i].y);
		diff.eb(b[i].y);
	}
	for (int i = 1; i <= m; ++i) {
		cin >> c[i].x >> c[i].y;
		sc.eb(c[i].x, mp(0, i));
		diff.eb(c[i].y);
	}
	sort(all(diff));
	diff.resize(unique(all(diff)) - diff.begin());
	int k = sz(diff);
	for (int i = 1; i <= n; ++i) {
		a[i].y = lower_bound(all(diff), a[i].y) - diff.begin();
		b[i].y = lower_bound(all(diff), b[i].y) - diff.begin();
	}
	for (int i = 1; i <= m; ++i) {
		c[i].y = lower_bound(all(diff), c[i].y) - diff.begin();
	}
	sort(all(sc));
	int i = 0;
	while (i < sz(sc)) {
		int j = i;
		while (j < sz(sc) && sc[i].x == sc[j].x) {
			int idx = sc[j].y.y;
			if (sc[j].y.x == -1) {
				cnt[idx] -= get_sum(0, 0, k, a[idx].y, b[idx].y + 1);
			} else if (sc[j].y.x == 0) {
				update(0, 0, k, c[idx].y, 1);
			} else {
				cnt[idx] += get_sum(0, 0, k, a[idx].y, b[idx].y + 1);
			}
			++j;
		}
		i = j;
	}
	for (int i = 1; i <= n; ++i) {
		cout << cnt[i] << "\n";
	}
	return 0;
}

Subtask #1
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 5416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 5672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 155 ms 8716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 11300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 226 ms 11300 KB Output isn't correct
2 Halted 0 ms 0 KB -