oj.uz

Submission #314293

# Submission time Handle Problem Language Result Execution time Memory
314293 2020-10-19T14:01:45 Z MetB Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 49904 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 () {
	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 < 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 29 ms 39864 KB Output is correct
2 Correct 35 ms 39876 KB Output is correct
3 Correct 99 ms 40128 KB Output is correct
4 Correct 249 ms 45912 KB Output is correct
5 Correct 156 ms 45880 KB Output is correct
6 Correct 30 ms 40124 KB Output is correct
7 Correct 30 ms 40124 KB Output is correct
8 Correct 29 ms 39872 KB Output is correct
9 Correct 28 ms 39852 KB Output is correct
10 Correct 29 ms 40004 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 42540 KB Output is correct
2 Correct 166 ms 43188 KB Output is correct
3 Correct 85 ms 41968 KB Output is correct
4 Correct 54 ms 41812 KB Output is correct
5 Correct 57 ms 43116 KB Output is correct
6 Correct 63 ms 42396 KB Output is correct
7 Correct 67 ms 42396 KB Output is correct
8 Correct 70 ms 42396 KB Output is correct
9 Correct 56 ms 42268 KB Output is correct
10 Correct 57 ms 42316 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39864 KB Output is correct
2 Correct 35 ms 39876 KB Output is correct
3 Correct 99 ms 40128 KB Output is correct
4 Correct 249 ms 45912 KB Output is correct
5 Correct 156 ms 45880 KB Output is correct
6 Correct 30 ms 40124 KB Output is correct
7 Correct 30 ms 40124 KB Output is correct
8 Correct 29 ms 39872 KB Output is correct
9 Correct 28 ms 39852 KB Output is correct
10 Correct 29 ms 40004 KB Output is correct
11 Correct 73 ms 42540 KB Output is correct
12 Correct 166 ms 43188 KB Output is correct
13 Correct 85 ms 41968 KB Output is correct
14 Correct 54 ms 41812 KB Output is correct
15 Correct 57 ms 43116 KB Output is correct
16 Correct 63 ms 42396 KB Output is correct
17 Correct 67 ms 42396 KB Output is correct
18 Correct 70 ms 42396 KB Output is correct
19 Correct 56 ms 42268 KB Output is correct
20 Correct 57 ms 42316 KB Output is correct
21 Correct 71 ms 42520 KB Output is correct
22 Correct 169 ms 43084 KB Output is correct
23 Correct 1092 ms 43400 KB Output is correct
24 Correct 2237 ms 48372 KB Output is correct
25 Correct 417 ms 48488 KB Output is correct
26 Correct 284 ms 49732 KB Output is correct
27 Correct 76 ms 45672 KB Output is correct
28 Correct 74 ms 45676 KB Output is correct
29 Execution timed out 4062 ms 49904 KB Time limit exceeded
30 Halted 0 ms 0 KB -