oj.uz

Submission #379789

# Submission time Handle Problem Language Result Execution time Memory
379789 2021-03-19T10:12:49 Z pit4h Dragon 2 (JOI17_dragon2) C++14
60 / 100
 923 ms 262148 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MAXN = 3e4+1, MAXQ = 1e5+1;
int n, m, t[MAXN], q, ans[MAXQ];

int sgn(ll x) {
	return (x>=0)?x? 1: 0: -1;
}
struct Point {
	int x, y;
	int id;
	Point() {}
	Point(int _x, int _y): x(_x), y(_y) {}
	void read() { cin>>x>>y; }
	Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); }
	
	bool operator<(const Point& o) const { return make_pair(x, y) < make_pair(o.x, o.y); }
	ll cross(const Point& o) {
		return (ll)x*o.y - (ll)y*o.x;
	}
	ll cross(const Point& o1, const Point& o2) {
		return (o1 - *this).cross(o2 - *this);
	}
};
Point O1, O2;
bool cmp(Point p1, Point p2) { // clockwise
	if(sgn(O1.cross(O2, p1)) != sgn(O1.cross(O2, p2))) {
		return (O1.cross(O2, p1) < 0LL)? true : false;
	}
	return O1.cross(p1, p2) < 0LL;
}
Point p[MAXN], pp[MAXN], s[MAXN];
vector<int> tribe[MAXN];
vector<pair<Point, int>> queries[MAXN];

int bit[MAXN];
void add(int idx, int delta) {
	assert(idx >= 0);
	for(; idx < n; idx = idx | (idx+1)) {
		bit[idx] += delta;
	}
}
int sum(int r) {
	assert(r >= 0);
	int res = 0;
	for(; r>=0; r = (r & (r+1)) - 1) {
		res += bit[r];
	}
	return res;
}
int sum(int l, int r) { 
	return sum(r) - ((l>0)?sum(l-1): 0);
}

void solve(vector<Point> pts, vector<pair<Point, int>> qs) {
	sort(pts.begin(), pts.end());
	sort(qs.begin(), qs.end());
	int j = 0;
	for(int i=0; i<(int)pts.size(); ++i) {
		while(j < (int)qs.size() && qs[j].st < pts[i]) {
			ans[qs[j].nd] += sum(0, qs[j].st.y-1);
			j++;
		}
		add(pts[i].y-1, 1);
	}
	while(j < (int)qs.size()) {
		ans[qs[j].nd] += sum(0, qs[j].st.y-1);
		j++;
	}
	for(int i=0; i<(int)pts.size(); ++i) {
		add(pts[i].y-1, -1);
	}
}

Point reflect(Point pt, Point o) {
	int dx = o.x - pt.x, dy = o.y - pt.y;
	pt.x += 2*dx, pt.y += 2*dy;
	return pt;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; ++i) {
		p[i].read();	
		p[i].id = i;
		cin>>t[i];
		tribe[t[i]].push_back(i);
	}
	Point P1, P2;
	P1.read(), P2.read();
	if(P2 < P1) swap(P1, P2);

	for(int i=1; i<=n; ++i) {
		if(P1.cross(P2, p[i]) > 0LL) {
			pp[i] = reflect(p[i], P1);	
		}
		else {
			pp[i] = p[i];
		}
	}
	O1 = P1, O2 = P2;
	sort(pp+1, pp+n+1, cmp);
	for(int i=1; i<=n; ++i) {
		s[pp[i].id].x = i;
	}
	
	for(int i=1; i<=n; ++i) { 
		if(P2.cross(P1, p[i]) < 0LL) {
			pp[i] = reflect(p[i], P2);	
		}
		else {
			pp[i] = p[i];
		}
	}
	O1 = P2, O2 = P1;
	sort(pp+1, pp+n+1, cmp);
	for(int i=1; i<=n; ++i) {
		s[pp[i].id].y = i;
	}

	cin>>q;
	for(int i=0; i<q; ++i) {
		int a, b; cin>>a>>b;
		/*if(tribe[a].size() > tribe[b].size()) {
			swap(a, b);
		}*/
		for(auto j: tribe[a]) {
			queries[b].push_back(mp(s[j], i));
		}
	}
	
	for(int i=1; i<=m; ++i) {
		vector<Point> up, down;
		vector<pair<Point, int>> upq, downq;
		for(auto j: tribe[i]) {
			if(P1.cross(P2, p[j]) < 0LL) {
				down.push_back(Point(s[j].x, n-s[j].y+1));
			}
			else {
				up.push_back(Point(n-s[j].x+1, s[j].y));
			}
		}
		for(auto j: queries[i]) {
			upq.push_back(mp(Point(n-j.st.x+1, j.st.y), j.nd));
			downq.push_back(mp(Point(j.st.x, n-j.st.y+1), j.nd));
		}
		solve(up, upq);
		solve(down, downq);
	}

	for(int i=0; i<q; ++i) {
		cout<<ans[i]<<'\n';
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2156 KB Output is correct
2 Correct 8 ms 2540 KB Output is correct
3 Correct 49 ms 5612 KB Output is correct
4 Correct 107 ms 12012 KB Output is correct
5 Correct 54 ms 6228 KB Output is correct
6 Correct 5 ms 2156 KB Output is correct
7 Correct 5 ms 2156 KB Output is correct
8 Correct 5 ms 2304 KB Output is correct
9 Correct 4 ms 2156 KB Output is correct
10 Correct 4 ms 2156 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5224 KB Output is correct
2 Correct 76 ms 8132 KB Output is correct
3 Correct 35 ms 4844 KB Output is correct
4 Correct 29 ms 4076 KB Output is correct
5 Correct 32 ms 4460 KB Output is correct
6 Correct 30 ms 5368 KB Output is correct
7 Correct 33 ms 5368 KB Output is correct
8 Correct 32 ms 5300 KB Output is correct
9 Correct 40 ms 5032 KB Output is correct
10 Correct 34 ms 5260 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2156 KB Output is correct
2 Correct 8 ms 2540 KB Output is correct
3 Correct 49 ms 5612 KB Output is correct
4 Correct 107 ms 12012 KB Output is correct
5 Correct 54 ms 6228 KB Output is correct
6 Correct 5 ms 2156 KB Output is correct
7 Correct 5 ms 2156 KB Output is correct
8 Correct 5 ms 2304 KB Output is correct
9 Correct 4 ms 2156 KB Output is correct
10 Correct 4 ms 2156 KB Output is correct
11 Correct 33 ms 5224 KB Output is correct
12 Correct 76 ms 8132 KB Output is correct
13 Correct 35 ms 4844 KB Output is correct
14 Correct 29 ms 4076 KB Output is correct
15 Correct 32 ms 4460 KB Output is correct
16 Correct 30 ms 5368 KB Output is correct
17 Correct 33 ms 5368 KB Output is correct
18 Correct 32 ms 5300 KB Output is correct
19 Correct 40 ms 5032 KB Output is correct
20 Correct 34 ms 5260 KB Output is correct
21 Correct 34 ms 5352 KB Output is correct
22 Correct 75 ms 7944 KB Output is correct
23 Correct 490 ms 31068 KB Output is correct
24 Correct 923 ms 68720 KB Output is correct
25 Correct 133 ms 13420 KB Output is correct
26 Correct 93 ms 8684 KB Output is correct
27 Correct 35 ms 5484 KB Output is correct
28 Correct 35 ms 5484 KB Output is correct
29 Runtime error 388 ms 262148 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -