Submission #314180

#	Time	Username	Problem	Language	Result	Execution time	Memory
314180		MetB	Dragon 2 (JOI17_dragon2)	C++14	0 / 100	131 ms	38088 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> > ords, orde;

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 (vector <pair <Pt, int>>& ord, Pt x) {
	return lower_bound (ord.begin(), ord.end(), make_pair (x,-1)) - ord.begin ();
}

int find_small (int i, int j) {

	int sum = 0, len = 0;

	//for (auto&& a : vs[j])
	//	cout << "(" << p[a].x << ", " << p[a].y << ")\n";

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

	vector < pair <Pt, int> > vp;

	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});
		//printf ("Points are (%lld,%lld)\n", vp.back ().first.x, vp.back ().first.y);
	}

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

	for (auto [p, x] : vp) {
		//printf ("Coming up point %d as (%lld, %lld)\n", x, p.x, p.y);

		while (len != vs[j].size () && (ps[*r] < -p || !p.up ())) {
			//cout << "Adding " << ps[*r].x << ' ' << ps[*r].y << endl;
			int x = find (orde, pe[*r]);
			len++;
			//cout << "As " << pe[*r].x << ' ' << pe[*r].y << ' ' << x << endl;
			t.update (x, 1);
			r++;

			if (r == vs[j].end ()) r = vs[j].begin ();
			if (l == r) full = true;
		}

		while (len && p.cross (ps[*l]) > 0) {
			//cout << "Deleting " << ps[*l].x << ' ' << ps[*l].y << endl;
			int x = find (orde, pe[*l]);
			len--;
			//cout << "As " << pe[*r].x << ' ' << pe[*r].y << ' ' << x << endl;
			t.update (x, -1);
			l++;

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

		auto ptr = l;
		//if (full) cout << "All of them" << endl;
		//{
		//	for (auto ptr = l; ptr != r; ptr++) {
		//		printf ("Having vector %d in it as (%lld,%lld)\n", *ptr, pe[*ptr].x, pe[*ptr].y);
		//		if (ptr == vs[j].end ()) ptr = vs[j].begin ();
		//	}
		//}

		//cout << "Try by " << pe[x].x << ' ' << pe[x].y << endl;

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

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

		//cout << l1 << ' ' << r1 << endl;

		if (l1 <= r1) sum += t.get (l1, r1);
		else sum += len - t.get (r1, l1);
		//cout << "New sum is " << sum << endl;
	}

	while (len) {
		//cout << "Deleting " << ps[*l].x << ' ' << ps[*l].y << endl;
		int x = find (orde, pe[*l]);
		t.update (x, -1);
		l++;
		len--;

		if (l == vs[j].end ()) l = vs[j].begin ();
		if (l == r) full = false;
	}

	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;
		ords.push_back ({ps[i], i});
		ords.push_back ({-ps[i], i});
		orde.push_back ({pe[i], i});
		orde.push_back ({-pe[i], i});
	}

	sort (ords.begin(), ords.end());
	sort (orde.begin(), orde.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:99:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |  for (auto [p, x] : vp) {
      |            ^
dragon2.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   while (len != vs[j].size () && (ps[*r] < -p || !p.up ())) {
      |          ~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:125:8: warning: variable 'ptr' set but not used [-Wunused-but-set-variable]
  125 |   auto ptr = l;
      |        ^~~
dragon2.cpp:87:7: warning: variable 'full' set but not used [-Wunused-but-set-variable]
   87 |  bool full = false;
      |       ^~~~

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