Submission #314184

#	Time	Username	Problem	Language	Result	Execution time	Memory
314184		MetB	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4094 ms	36716 KiB

dragon2

#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 < pair <Pt, int> > ord;

map <int, ll> ans[N];

ll big[N], sz[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 find_small (int i, int j) {

	ll sum = 0, len = 0;

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

	vector < pair <Pt, int> > vp;
	vector <int> deleted (vs[j].size ());

	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) sum += (ll) t.get (l1, r1);
		else sum += (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);
		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];

		sz[i] = v[i].size ();

		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--;
		cout << find_small (a, b) << endl;
	}
}	

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40