oj.uz

Submission #314184

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

	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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33592 KB Output is correct
2 Correct 41 ms 33604 KB Output is correct
3 Correct 166 ms 33608 KB Output is correct
4 Correct 589 ms 33844 KB Output is correct
5 Correct 440 ms 33848 KB Output is correct
6 Correct 37 ms 33728 KB Output is correct
7 Correct 36 ms 33720 KB Output is correct
8 Correct 31 ms 33528 KB Output is correct
9 Correct 28 ms 33604 KB Output is correct
10 Correct 28 ms 33532 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 36008 KB Output is correct
2 Correct 272 ms 35460 KB Output is correct
3 Correct 135 ms 35440 KB Output is correct
4 Correct 108 ms 35308 KB Output is correct
5 Correct 110 ms 36716 KB Output is correct
6 Correct 112 ms 35996 KB Output is correct
7 Correct 114 ms 35868 KB Output is correct
8 Correct 115 ms 35868 KB Output is correct
9 Correct 93 ms 35868 KB Output is correct
10 Correct 95 ms 36012 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33592 KB Output is correct
2 Correct 41 ms 33604 KB Output is correct
3 Correct 166 ms 33608 KB Output is correct
4 Correct 589 ms 33844 KB Output is correct
5 Correct 440 ms 33848 KB Output is correct
6 Correct 37 ms 33728 KB Output is correct
7 Correct 36 ms 33720 KB Output is correct
8 Correct 31 ms 33528 KB Output is correct
9 Correct 28 ms 33604 KB Output is correct
10 Correct 28 ms 33532 KB Output is correct
11 Correct 118 ms 36008 KB Output is correct
12 Correct 272 ms 35460 KB Output is correct
13 Correct 135 ms 35440 KB Output is correct
14 Correct 108 ms 35308 KB Output is correct
15 Correct 110 ms 36716 KB Output is correct
16 Correct 112 ms 35996 KB Output is correct
17 Correct 114 ms 35868 KB Output is correct
18 Correct 115 ms 35868 KB Output is correct
19 Correct 93 ms 35868 KB Output is correct
20 Correct 95 ms 36012 KB Output is correct
21 Correct 119 ms 36120 KB Output is correct
22 Correct 277 ms 35456 KB Output is correct
23 Correct 1878 ms 35572 KB Output is correct
24 Execution timed out 4094 ms 35816 KB Time limit exceeded
25 Halted 0 ms 0 KB -