Submission #467537

#	Time	Username	Problem	Language	Result	Execution time	Memory
467537		pure_mem	Dragon 2 (JOI17_dragon2)	C++14	0 / 100	28 ms	10432 KiB

dragon2

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int maxN = 3e4 + 12, maxQ = 1e5 + 12, block = 0;

typedef pair<ll, ll> Point;

int half(Point a, Point b) {
	if(a.X != b.X) return a.X < b.X ? 1: -1;
	return a.Y < b.Y ? 1: -1;
}
int sign(ll val) {
	if(val < 0) return -1;
	if(val == 0) return 0;
	return 1;
}

ll cross(Point a, Point b, Point c) { 
	a.X -= c.X, a.Y -= c.Y;
	b.X -= c.X, b.Y -= c.Y;
	return a.X * b.Y - a.Y * b.X;
}

struct Fenwick {
	int f[maxN], was[maxN], timer = 0;
	void upd(int v, int val) {
		for(;v < maxN;v |= v + 1) {
			if(was[v] != timer)
				was[v] = timer, f[v] = 0;
			f[v] += val;
		}
	}
	int get(int v) {
		int res = 0;
		for(;v >= 0;v = (v & (v + 1)) - 1) {
			if(was[v] != timer)
				was[v] = timer, f[v] = 0;
			res += f[v];
		}
		return res;
	}
	int get(int l, int r) {
		if(r >= maxN) r = maxN - 1;
		return get(r) - get(l - 1);
	}
} fw;

struct Event {
	int i, id, pr;
	Point pos;
} p[maxN], events[maxN];
pair<Point, Point> city;
int n, m, q, qCnt[maxN], eLen;
ll answer[maxQ], tAnswer[maxN];
vector< pair<int, int> > query1[maxN], query2[maxN];
vector< int > g[maxN];

void inputs() {
	cin >> n >> m;
	for(int i = 1, x, y, id;i <= n;i++) {
		cin >> x >> y >> id;
		p[i] = {id, id, 0, {x, y}};		
   	}
   	cin >> city.X.X >> city.X.Y >> city.Y.X >> city.Y.Y >> q;
}

void prepare1() {
	sort(p + 1, p + n + 1, 
		[](const Event &lhs, const Event &rhs){
			if(half(lhs.pos, city.Y) != half(rhs.pos, city.Y))
				return half(lhs.pos, city.Y) < half(rhs.pos, city.Y);
			return cross(lhs.pos, rhs.pos, city.Y) < 0;	
		}
	);
	for(int i = 1;i <= n;i++) p[i].id = i;
	for(int i = 1, cnt = 0, ptr = i;i <= n;i++) {
		while(cnt <= n && sign(cross(p[i].pos, city.Y, p[ptr].pos)) * sign(cross(p[i].pos, city.Y, city.X)) != -1) {
			cnt++;
			ptr = (ptr == n ? 1: ptr + 1);
		}
		cnt--;
		if(cnt) p[i].pr = (cnt == n ? n - 1: cnt);			
		if(cnt == n) cnt = 0;
	}
	for(int i = n, cnt = 0, ptr = n;i >= 1;i--){
		while(cnt <= n && sign(cross(p[i].pos, city.Y, p[ptr].pos)) * sign(cross(p[i].pos, city.Y, city.X)) != -1) {
			cnt++;
			ptr = (ptr == 1 ? n: ptr - 1);
		}
		cnt--;
		if(cnt && !p[i].pr) p[i].pr = (cnt == n ? -n + 1: -cnt);				
		if(cnt == n) cnt = 0;
	}
}

void prepare2() {
	for(int i = 1;i <= n;i++) {
	//	cerr << p[i].pos.X << " " << p[i].pos.Y << " " << p[i].pr << "\n";
	}
	
	sort(p + 1, p + n + 1, 
		[](const Event &lhs, const Event &rhs){
			if(half(lhs.pos, city.X) != half(rhs.pos, city.X))
				return half(lhs.pos, city.X) < half(rhs.pos, city.X);
			return cross(lhs.pos, rhs.pos, city.X) < 0;	
		}
	);
	for(int i = 1;i <= n;i++){
		g[p[i].i].push_back(i);
	}
}

int was[maxN], timer;
void solve(int atk) {
	timer++, fw.timer++;
	for(int i = 1, cnt = 0, ptr = 1;i <= eLen;i++) {
		while(cnt <= n && sign(cross(p[i].pos, city.X, p[ptr].pos)) * sign(cross(p[i].pos, city.X, city.Y)) != -1) {
			cnt++;
			if((atk > 0 && p[ptr].i != atk) || (p[ptr].i == -atk))
				fw.upd(p[ptr].id, 1);
			ptr = (ptr == eLen ? 1: ptr + 1);
		}	
		cnt--;
		//cerr << p[i].pos.X << " " << p[i].pos.Y << " " << cnt << "\n";
		if((atk > 0 && p[i].i != atk) || (p[i].i == -atk))
			fw.upd(p[i].id, -1);
		else if(cnt){
			if(p[i].pr > 0) {
				tAnswer[p[i].i] += fw.get(p[i].id, p[i].id + p[i].pr);
				if(p[i].id + p[i].pr > n)
					tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr - n);					
			} 
			else if(p[i].pr < 0) {
				tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr, p[i].id);
				if(p[i].id + p[i].pr < 1)
					tAnswer[p[i].i] += fw.get(n - (p[i].id + p[i].pr), n);					
			}
			was[i] = timer;
		}
		if(cnt == n) fw.timer++, cnt = 0;
	}
	fw.timer++;
	for(int i = eLen, cnt = 0, ptr = eLen;i >= 1;i--) {
		while(cnt <= n && sign(cross(p[i].pos, city.X, p[ptr].pos)) * sign(cross(p[i].pos, city.X, city.Y)) != -1) {
			cnt++;
			if((atk > 0 && p[ptr].i != atk) || (p[ptr].i == -atk))
				fw.upd(p[ptr].id, 1);
			ptr = (ptr == 1 ? eLen: ptr - 1);
		}	
		cnt--;
		if((atk > 0 && p[i].i != atk) || (p[i].i == -atk))
			fw.upd(p[i].id, -1);
		else if(cnt && was[i] != timer){
			if(p[i].pr > 0) {
				tAnswer[p[i].i] += fw.get(p[i].id, p[i].id + p[i].pr);
				if(p[i].id + p[i].pr > n)
					tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr - n);					
			} 
			else if(p[i].pr < 0) {
				tAnswer[p[i].i] += fw.get(p[i].id + p[i].pr, p[i].id);
				if(p[i].id + p[i].pr < 1)
					tAnswer[p[i].i] += fw.get(n - (p[i].id + p[i].pr), n);					
			}
			assert(was[i] != timer);
			was[i] = timer;
		}
		if(cnt == n) fw.timer++, cnt = 0;
	}	
}

void prepare(int me) {
	memset(tAnswer, 0, sizeof(tAnswer));
	solve(me), solve(-me);	
	for(pair<int, int> v: query1[me]) {
		if(answer[v.Y] == -1) {
			answer[v.Y] = tAnswer[me];
		}
	}
	for(pair<int, int> v: query2[me]) {
		if(answer[v.Y] == -1) {
			answer[v.Y] = tAnswer[v.X];
		}
	}
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	inputs();
	prepare1();
	prepare2();
	for(int i = 1, u, v;i <= q;i++) {
   		cin >> u >> v;
   		query1[u].push_back(MP(v, i));
   		query2[v].push_back(MP(u, i));
   		answer[i] = -1;
   	}
   	for(int i = 1;i <= n;i++)
		events[i] = p[i];
	eLen = n;
   	for(int i = 1;i <= m;i++) {
   		if(query1[i].size() + query2[i].size() >= block) {
   			prepare(i);
   		}			
   	}
   	for(int i = 1;i <= q;i++) {
   		cout << answer[i] << "\n";
   	}
}

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