oj.uz

Submission #314292

# Submission time Handle Problem Language Result Execution time Memory
314292 2020-10-19T14:00:04 Z MetB Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 51560 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];

unordered_map <int, int> qu[N];

int n, m, q, bl = 400;

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;

	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 = find (pe[*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 = find (pe[*r]);
			t.update (x, 1);
			r++, len++;
		}

		while (l != vs[j].end () && len && ps[*l] < p) {
			int x = find (pe[*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 = find (pe[*l]);
		t.update (x, -1);
		l++, len--;
		if (l == vs[j].end ()) l = vs[j].begin ();
	}

	return sum;
}

int main () {
	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 < 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:85:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for (auto [p, x] : vp) {
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39872 KB Output is correct
2 Correct 43 ms 39996 KB Output is correct
3 Correct 113 ms 40384 KB Output is correct
4 Correct 343 ms 46648 KB Output is correct
5 Correct 250 ms 46776 KB Output is correct
6 Correct 39 ms 40248 KB Output is correct
7 Correct 38 ms 40248 KB Output is correct
8 Correct 38 ms 39872 KB Output is correct
9 Correct 35 ms 39996 KB Output is correct
10 Correct 35 ms 39876 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 43180 KB Output is correct
2 Correct 234 ms 43820 KB Output is correct
3 Correct 141 ms 42608 KB Output is correct
4 Correct 116 ms 42732 KB Output is correct
5 Correct 120 ms 43756 KB Output is correct
6 Correct 123 ms 43032 KB Output is correct
7 Correct 126 ms 43036 KB Output is correct
8 Correct 124 ms 43032 KB Output is correct
9 Correct 101 ms 42780 KB Output is correct
10 Correct 102 ms 42796 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39872 KB Output is correct
2 Correct 43 ms 39996 KB Output is correct
3 Correct 113 ms 40384 KB Output is correct
4 Correct 343 ms 46648 KB Output is correct
5 Correct 250 ms 46776 KB Output is correct
6 Correct 39 ms 40248 KB Output is correct
7 Correct 38 ms 40248 KB Output is correct
8 Correct 38 ms 39872 KB Output is correct
9 Correct 35 ms 39996 KB Output is correct
10 Correct 35 ms 39876 KB Output is correct
11 Correct 126 ms 43180 KB Output is correct
12 Correct 234 ms 43820 KB Output is correct
13 Correct 141 ms 42608 KB Output is correct
14 Correct 116 ms 42732 KB Output is correct
15 Correct 120 ms 43756 KB Output is correct
16 Correct 123 ms 43032 KB Output is correct
17 Correct 126 ms 43036 KB Output is correct
18 Correct 124 ms 43032 KB Output is correct
19 Correct 101 ms 42780 KB Output is correct
20 Correct 102 ms 42796 KB Output is correct
21 Correct 126 ms 43164 KB Output is correct
22 Correct 222 ms 43732 KB Output is correct
23 Correct 1194 ms 44340 KB Output is correct
24 Correct 2461 ms 49228 KB Output is correct
25 Correct 578 ms 50160 KB Output is correct
26 Correct 437 ms 51560 KB Output is correct
27 Correct 150 ms 46572 KB Output is correct
28 Correct 150 ms 46568 KB Output is correct
29 Execution timed out 4085 ms 51548 KB Time limit exceeded
30 Halted 0 ms 0 KB -