oj.uz

Submission #314295

# Submission time Handle Problem Language Result Execution time Memory
314295 2020-10-19T14:13:07 Z MetB Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 78940 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
 
#define N 200001
 
using namespace std;
 
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

struct Pt {
	ll x, y;

	Pt (int x, int y) : x (x), y (y) {}
	Pt () : x (0), y (0) {}

	ll cross (const Pt& b) const { return x * b.y - b.x * y; }
	bool up () const { return y > 0 or (y == 0 and x >= 0); }
	bool operator < (const Pt& b) const { return up() == b.up() ? cross (b) < 0 : up() > b.up(); }
	Pt operator - (const Pt& b) const { return Pt (x - b.x, y - b.y); }
	Pt operator - () const { return Pt (-x, -y); }
} s, e;

vector <int> vs[N], ve[N], v[N];
Pt p[N], pe[N], ps[N];
vector <int> to[N];

vector < pair <Pt, int> > ord;

ll ans[N], gr[N];

gp_hash_table <int, int> qu[N];

int n, m, q, srt[N];

struct BIT {
	int t[N];

	void update (int x, int d) {
		for (; x < N; x = (x | (x + 1)))
			t[x] += d;
	}

	int get (int r) {
		int sum = 0;

		for (; r >= 0; r = (r & (r + 1)) - 1)
			sum += t[r];

		return sum;
	}

	int get (int l, int r) { return get (r) - get (l - 1); }
} t;

int find (Pt x) {
	return lower_bound (ord.begin(), ord.end(), make_pair (x,-1)) - ord.begin ();
}

int fight (int j) {

	ll sum = 0, len = 0;

	auto l = vs[j].begin (), r = vs[j].begin ();

	vector < pair <Pt, int> > vp;

	sort (to[j].begin(), to[j].end());
	to[j].erase (unique (to[j].begin(), to[j].end()), to[j].end ());

	for (int i : to[j]) {
		for (int x : v[i]) {
			if (ps[x].cross (e - s) > 0) vp.push_back ({-ps[x], x});
			else vp.push_back ({ps[x], x});
		}
	}

	sort (vp.begin(), vp.end());

	auto prev = vp[0].first;

	for (auto [p, x] : vp) {

		int limit = vs[j].size ();

		if (-p < prev) {
			while (r != vs[j].end ()) {
				int x = srt[*r];
				t.update (x, 1);
				r++, len++;
			}
			r = vs[j].begin ();
			limit += vs[j].size ();
		}
		prev = -p;

		while (r != vs[j].end () && len != limit && ps[*r] < -p) {
			int x = srt[*r];
			t.update (x, 1);
			r++, len++;
		}

		while (l != vs[j].end () && len && ps[*l] < p) {
			int x = srt[*l];
			t.update (x, -1);
			l++, len--;
		}

		int l1 = find (pe[x]), r1 = find (-pe[x]);

		if (pe[x].cross (s - e) > 0) swap (l1, r1);

		if (l1 <= r1) ans[qu[gr[x]][j]] += (ll) t.get (l1, r1);
		else ans[qu[gr[x]][j]] += (ll) len - t.get (r1, l1);
	}

	if (l == vs[j].end ()) l = vs[j].begin ();

	while (len) {
		int x = srt[*l];
		t.update (x, -1);
		l++, len--;
		if (l == vs[j].end ()) l = vs[j].begin ();
	}

	return sum;
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie (0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		p[i] = Pt (a, b);
		gr[i] = c - 1;
		v[c-1].push_back (i);
	}

	int x, y;

	cin >> x >> y;
	s = Pt (x, y);

	cin >> x >> y;
	e = Pt (x, y);

	for (int i = 0; i < n; i++) {
		ps[i] = p[i] - s;
		pe[i] = p[i] - e;
		ord.push_back ({pe[i], i});
		ord.push_back ({-pe[i], i});
	}

	sort (ord.begin(), ord.end());

	for (int i = 0; i < n; i++) {
		srt[i] = find (pe[i]);
	}

	for (int i = 0; i < m; i++) {
		vs[i] = v[i];
		ve[i] = v[i];

		sort (vs[i].begin(), vs[i].end(), [&](int a, int b) { return ps[a] < ps[b]; });
		sort (ve[i].begin(), ve[i].end(), [&](int a, int b) { return pe[a] < pe[b]; });
	}

	cin >> q;

	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		to[b].push_back (a);
		qu[a][b] = i;
	}

	for (int i = 0; i < m; i++) {
		fight (i);
	}

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

Compilation message

dragon2.cpp: In function 'int fight(int)':
dragon2.cpp:88:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |  for (auto [p, x] : vp) {
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 71228 KB Output is correct
2 Correct 76 ms 71356 KB Output is correct
3 Correct 137 ms 71484 KB Output is correct
4 Correct 256 ms 76088 KB Output is correct
5 Correct 177 ms 76984 KB Output is correct
6 Correct 69 ms 71352 KB Output is correct
7 Correct 69 ms 71352 KB Output is correct
8 Correct 72 ms 71224 KB Output is correct
9 Correct 69 ms 71232 KB Output is correct
10 Correct 70 ms 71160 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 73900 KB Output is correct
2 Correct 203 ms 74548 KB Output is correct
3 Correct 126 ms 73324 KB Output is correct
4 Correct 102 ms 73324 KB Output is correct
5 Correct 102 ms 74468 KB Output is correct
6 Correct 108 ms 73884 KB Output is correct
7 Correct 110 ms 73756 KB Output is correct
8 Correct 112 ms 73756 KB Output is correct
9 Correct 96 ms 73756 KB Output is correct
10 Correct 99 ms 73776 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 71228 KB Output is correct
2 Correct 76 ms 71356 KB Output is correct
3 Correct 137 ms 71484 KB Output is correct
4 Correct 256 ms 76088 KB Output is correct
5 Correct 177 ms 76984 KB Output is correct
6 Correct 69 ms 71352 KB Output is correct
7 Correct 69 ms 71352 KB Output is correct
8 Correct 72 ms 71224 KB Output is correct
9 Correct 69 ms 71232 KB Output is correct
10 Correct 70 ms 71160 KB Output is correct
11 Correct 115 ms 73900 KB Output is correct
12 Correct 203 ms 74548 KB Output is correct
13 Correct 126 ms 73324 KB Output is correct
14 Correct 102 ms 73324 KB Output is correct
15 Correct 102 ms 74468 KB Output is correct
16 Correct 108 ms 73884 KB Output is correct
17 Correct 110 ms 73756 KB Output is correct
18 Correct 112 ms 73756 KB Output is correct
19 Correct 96 ms 73756 KB Output is correct
20 Correct 99 ms 73776 KB Output is correct
21 Correct 112 ms 73984 KB Output is correct
22 Correct 203 ms 74572 KB Output is correct
23 Correct 1076 ms 74968 KB Output is correct
24 Correct 2151 ms 78940 KB Output is correct
25 Correct 417 ms 78696 KB Output is correct
26 Correct 296 ms 78568 KB Output is correct
27 Correct 116 ms 76164 KB Output is correct
28 Correct 113 ms 76140 KB Output is correct
29 Execution timed out 4046 ms 78572 KB Time limit exceeded
30 Halted 0 ms 0 KB -