oj.uz

Submission #314183

# Submission time Handle Problem Language Result Execution time Memory
314183 2020-10-19T01:02:19 Z MetB Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 37612 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 < 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;

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

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

	auto prev = vp[0].first;

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

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

		if (-p < prev) {
			while (r != vs[j].end ()) {
				//cout << "Adding " << ps[*r].x << ' ' << ps[*r].y << endl;
				int x = find (pe[*r]);
				len++;
				//cout << "As " << pe[*r].x << ' ' << pe[*r].y << ' ' << x << endl;
				t.update (x, 1);
				r++;
			}
			r = vs[j].begin ();
			limit += vs[j].size ();
		}
		prev = -p;

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

			if (l == r) full = true;
		}

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

		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 (pe[x]), r1 = find (-pe[x]);

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

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

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

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

	while (len) {
		//cout << "Deleting " << ps[*l].x << ' ' << ps[*l].y << endl;
		int x = find (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;
		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

dragon2.cpp: In function 'int find_small(int, int)':
dragon2.cpp:102:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |  for (auto [p, x] : vp) {
      |            ^
dragon2.cpp:141:8: warning: variable 'ptr' set but not used [-Wunused-but-set-variable]
  141 |   auto ptr = l;
      |        ^~~
dragon2.cpp:87:7: warning: variable 'full' set but not used [-Wunused-but-set-variable]
   87 |  bool full = false;
      |       ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33600 KB Output is correct
2 Correct 42 ms 33600 KB Output is correct
3 Correct 164 ms 33728 KB Output is correct
4 Correct 597 ms 34744 KB Output is correct
5 Correct 443 ms 35000 KB Output is correct
6 Correct 37 ms 33728 KB Output is correct
7 Correct 37 ms 33720 KB Output is correct
8 Correct 31 ms 33600 KB Output is correct
9 Correct 29 ms 33604 KB Output is correct
10 Correct 28 ms 33612 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 36028 KB Output is correct
2 Correct 276 ms 36100 KB Output is correct
3 Correct 137 ms 36080 KB Output is correct
4 Correct 106 ms 36076 KB Output is correct
5 Correct 111 ms 37612 KB Output is correct
6 Correct 113 ms 36736 KB Output is correct
7 Correct 116 ms 36680 KB Output is correct
8 Correct 116 ms 36508 KB Output is correct
9 Correct 93 ms 36380 KB Output is correct
10 Correct 97 ms 36396 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33600 KB Output is correct
2 Correct 42 ms 33600 KB Output is correct
3 Correct 164 ms 33728 KB Output is correct
4 Correct 597 ms 34744 KB Output is correct
5 Correct 443 ms 35000 KB Output is correct
6 Correct 37 ms 33728 KB Output is correct
7 Correct 37 ms 33720 KB Output is correct
8 Correct 31 ms 33600 KB Output is correct
9 Correct 29 ms 33604 KB Output is correct
10 Correct 28 ms 33612 KB Output is correct
11 Correct 117 ms 36028 KB Output is correct
12 Correct 276 ms 36100 KB Output is correct
13 Correct 137 ms 36080 KB Output is correct
14 Correct 106 ms 36076 KB Output is correct
15 Correct 111 ms 37612 KB Output is correct
16 Correct 113 ms 36736 KB Output is correct
17 Correct 116 ms 36680 KB Output is correct
18 Correct 116 ms 36508 KB Output is correct
19 Correct 93 ms 36380 KB Output is correct
20 Correct 97 ms 36396 KB Output is correct
21 Correct 121 ms 36764 KB Output is correct
22 Correct 277 ms 36088 KB Output is correct
23 Correct 1888 ms 36208 KB Output is correct
24 Execution timed out 4067 ms 37492 KB Time limit exceeded
25 Halted 0 ms 0 KB -