Submission #467736

#	Time	Username	Problem	Language	Result	Execution time	Memory
467736		pure_mem	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4094 ms	22404 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 = 6e4 + 12;
const int maxQ = 1e5 + 12;
const int block = 300, INF = 1e9 + 7;
 
typedef pair<ll, ll> Point;
Point origin;
 
struct Fenwick {
	int f[maxN], was[maxN], timer = 0;
	void clear() {
		timer++;
	}
	void upd(int v, int val) {
		for(;v < maxN;v |= v + 1) {
			if(was[v] != timer)
				f[v] = 0, was[v] = timer;
			f[v] += val;
	    }
	}
	int get(int v) {
		int res = 0;
		for(;v >= 0;v = (v & (v + 1)) - 1) {
			if(was[v] != timer)
				f[v] = 0, was[v] = timer;
			res += f[v];
		}
		return res;
	}
	int get(int l, int r) {
		if(l > r) {
			return get(maxN - 1) - get(l - 1) + get(r);
		} 
		else {
		    return get(r) - get(l - 1);
		}
	}
} BIT;

struct node {
	int s = 0;
	node *l = nullptr, *r = nullptr;	
};
int tree_ptr;
node* tree[maxN];

node* upd(node* v, int tl, int tr, int pos, int val) {
	if(tl == tr) 
		return new node {(v ? v->s: 0) + val, nullptr, nullptr};
	int tm = (tl + tr) / 2;
	if(pos <= tm) {	
		return new node {(v ? v->s: 0) + val, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v};
	}
	else {
		return new node {(v ? v->s: 0) + val, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val)};
	}
}
int get(node* v, int tl, int tr, int l, int r){
	if(!v || tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return v->s;
	int tm = (tl + tr) / 2;
	return get(v->l, tl, tm, l, r) + get(v->r, tm + 1, tr, l, r);
}
 
int sign(ll value) {
	if(value > 0) return 1;
	if(value < 0) return -1;
	return 0;
}
 
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;
}
 
ll cross(Point a, Point b, Point c) {
	a.X -= c.X, b.X -= c.X;
	a.Y -= c.Y, b.Y -= c.Y;
	return a.X * b.Y - a.Y * b.X;
}
 
struct Event {
	int clr, id;
	Point pos;
};
 
bool operator < (const Event &lhs, const Event &rhs) {
	int lhs_h = half(lhs.pos, origin);
	int rhs_h = half(rhs.pos, origin);
	if(lhs_h != rhs_h)
		return lhs_h < rhs_h;
	return cross(lhs.pos, rhs.pos, origin) < 0;
}
 
int n, m, q, tValue[maxN], txValue[maxN];
ll answer[maxQ];
pair< Point, Point > city;
pair< int, int > border[maxN], xBorder[maxN];
vector< pair<int, int> > rQuery[maxN], Query[maxN];
vector< int > gDragon[maxN];
Event dragon[maxN];
 
// border - y, area - x
 
void inputs() {
	memset(answer, -1, sizeof(answer));
	cin >> n >> m;
	for(int i = 1, x, y, clr;i <= n;i++){
		cin >> x >> y >> clr;
	//	x += INF, y += INF;
		dragon[i] = {clr, i, {x, y}};
		dragon[i + n] = {-clr, i, {-x, -y}};		
	}
	cin >> city.X.X >> city.X.Y >> city.Y.X >> city.Y.Y;
	cin >> q;
	for(int i = 1, u, v;i <= q;i++){
		cin >> u >> v;
		Query[u].push_back({v, i});
		rQuery[v].push_back({u, i});
	}
}
 
void normalize() {
	for(int i = 1;i <= n + n;i++) {
		if(dragon[i].clr > 0) {
			dragon[i].pos.X -= origin.X;	
			dragon[i].pos.Y -= origin.Y;
		}	
		else {
		    dragon[i].pos.X += origin.X;	
			dragon[i].pos.Y += origin.Y;
		}
	}
	city.X.X -= origin.X, city.Y.X -= origin.X;
	city.X.Y -= origin.Y, city.Y.Y -= origin.Y;
}
void d_normalize() {
	for(int i = 1;i <= n + n;i++) {
		if(dragon[i].clr > 0) {
			dragon[i].pos.X += origin.X;	
			dragon[i].pos.Y += origin.Y;
		}	
		else {
		    dragon[i].pos.X -= origin.X;	
			dragon[i].pos.Y -= origin.Y;
		}
	}
	city.X.X += origin.X, city.Y.X += origin.X;
	city.X.Y += origin.Y, city.Y.Y += origin.Y;
}
 
void prepare() {
	origin = city.Y;
	auto mem = origin;
	normalize(), origin = MP(0, 0);
	sort(dragon + 1, dragon + n + n + 1);
	for(int i = 1, id;i <= n + n;i++){
		id = dragon[i].id;
		if(dragon[i].clr > 0)
			tValue[id] = i, txValue[i] = id;
		if(border[id].X == 0)	
			border[id].X = i;
		else
			border[id].Y = i;	
	}
	for(int i = 1;i <= n;i++) {
		Event cur = dragon[border[i].X];
		Event rev = dragon[border[i].Y];
		if(cross(cur.pos, rev.pos, city.X) < 0)	
			swap(border[i].X, border[i].Y);
		//cerr << i << ": " << border[i].X << " " << border[i].Y << "\n";
	}
	origin = mem;
	d_normalize();
	
	origin = city.X, mem = origin;
	normalize(), origin = MP(0, 0);
	sort(dragon + 1, dragon + n + n + 1);
	for(int i = 1, id;i <= n + n;i++) {
		gDragon[abs(dragon[i].clr)].push_back(i);
		id = dragon[i].id;
		if(xBorder[id].X == 0)
			xBorder[id].X = i;
		else
			xBorder[id].Y = i;	
	}   /*
	for(int i = 1;i <= n + n;i++) {
		int val = 0;
		if(dragon[i].clr < 0) continue;
		cerr << dragon[i].id << " " << i << "\n";
	}   */
	for(int i = 1;i <= n;i++) {
		const Event& cur = dragon[xBorder[i].X];
		const Event& rev = dragon[xBorder[i].Y];
		if(cross(cur.pos, rev.pos, city.Y) < 0)	
			swap(xBorder[i].X, xBorder[i].Y);
		//cerr << i << ": " << xBorder[i].X << " " << xBorder[i].Y << "\n";
	}
 
 
}
 
void add_interval(pair<int, int> v, int val) {
	if(v.X <= v.Y) {
		BIT.upd(v.X, val);
		BIT.upd(v.Y + 1, -val);
	}
	else {
		BIT.upd(v.X, val);
		BIT.upd(1, val);
		BIT.upd(v.Y + 1, -val);
	}
}
 
ll tAnswer[maxN];
int tDragon[maxN], act[maxN];
void solveHeavy(int atk) {
	memset(tAnswer, 0, sizeof(tAnswer));		
	memset(act, 0, sizeof(act));
	BIT.clear();
	for(int it = 0;it < 2;it++){
    	for(int i = 1;i <= n + n;i++) {
    		const Event& cur = dragon[i];
    		if(cur.clr < 0 && cur.clr != -atk)
    			continue;	
    		if(abs(cur.clr) != atk) {
    			if(it == 1)
    				tAnswer[cur.clr] += BIT.get(tValue[cur.id]);
    			//cerr << tAnswer[cur.clr] << "\n";
    		}
    		else if(i == xBorder[cur.id].X) {
  				if(!act[cur.id]) { 
  					act[cur.id] = 1;
  					add_interval(border[cur.id], 1);
    			}	
    		}
    		else {
   				if(act[cur.id]) {
   					act[cur.id] = 0;
   					add_interval(border[cur.id], -1);
   				}
   			}	
    	}
	}
	for(pair<int, int> v: Query[atk]) {
		if(answer[v.Y] != -1) 
			continue;
		answer[v.Y] = tAnswer[v.X];	
	}
}

int get(int x, int l, int r){
	if(l <= r)
		return get(tree[x], 1, n + n, l, r);
	//cerr << get(tree[x], 1, n + n, l, n + n) << " " << get(tree[x], 1, n + n, 1, r) << " = ";
	return get(tree[x], 1, n + n, l, n + n) + get(tree[x], 1, n + n, 1, r);		
}

int get(int xl, int xr, int l, int r) {
//	cerr << xl << " " << xr << " " << l << " " << r << "\n";
	if(xl <= xr)
		return get(xr, l, r) - get(xl - 1, l, r);
	//cerr << "1: " << get(n + n, l, r) << "\n2: " << get(xr - 1, l, r) << "\n3: " << get(xl, l, r) << "\n";
	return get(n + n, l, r) - get(xl - 1, l, r) + get(xr, l, r); 
}

void solveHeavyR(int atk) {
	for(int i = 1;i <= n + n;i++) {
		tree[i] = tree[i - 1];
		int id = dragon[i].id;
		if(dragon[i].clr == atk) {
		//	cerr << i << " " << tValue[id] << "\n";
			tree[i] = upd(tree[i], 1, n + n, tValue[id], 1);
		}	
	}
	for(pair<int, int> v: rQuery[atk]) {
		if(answer[v.Y] != -1)
			continue;
		answer[v.Y] = 0;
		for(int i: gDragon[v.X]) {
			if(dragon[i].clr < 0) continue;
			int id = dragon[i].id;
			int add = get(xBorder[id].X, xBorder[id].Y, border[id].X, border[id].Y);	
			
			answer[v.Y] += add;		
		}
	} 		
}
 
ll solveLight(int atk, int def) {		
	int lens = gDragon[atk].size() + gDragon[def].size();
	ll res = 0;
	merge(gDragon[atk].begin(), gDragon[atk].end(),
		  gDragon[def].begin(), gDragon[def].end(), tDragon + 1);
	BIT.clear();
	for(int it = 0;it < 2;it++){
    	for(int i = 1;i <= lens;i++) {
    		const Event& cur = dragon[tDragon[i]];
    		if(-cur.clr == def)
    			continue;	
    		if(cur.clr == def) {
    			if(it == 1)
    				res += BIT.get(tValue[cur.id]);
    		//	cerr << cur.id << " " << tValue[cur.id] << "gg\n";
    		}
    		else if(tDragon[i] == xBorder[cur.id].X) {
  				if(!act[cur.id]) { 
  					act[cur.id] = 1;
  			//		cerr << cur.id << " " << border[cur.id].X << " " << border[cur.id].Y << "was+\n";
  					add_interval(border[cur.id], 1);
    			}	
    		}
    		else {
   				if(act[cur.id]) {
   					act[cur.id] = 0;
   			//		cerr << cur.id << " " << border[cur.id].X << " " << border[cur.id].Y << "was-\n";
   					add_interval(border[cur.id], -1);
   				}
   			}	
    	}
	}
	for(int i = 1;i <= lens;i++) {
    	const Event& cur = dragon[tDragon[i]];
    	act[cur.id] = 0;
    }
    return res;
}
 
int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	inputs();
	prepare();
	for(int i = 1;i <= m;i++) {
		if(rQuery[i].size() >= block)
			solveHeavy(i), solveHeavyR(i);
	}
	for(int i = 1;i <= m;i++) {
		for(pair<int, int> v: Query[i]) {
			if(answer[v.Y] != -1) 
				continue;
			answer[v.Y] = solveLight(i, v.X);
		}
	}
	for(int i = 1;i <= q;i++)
		cout << answer[i] << "\n";
}

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