oj.uz

Submission #467736

# Submission time Handle Problem Language Result Execution time Memory
467736 2021-08-24T08:59:03 Z pure_mem Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 22404 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6988 KB Output is correct
2 Correct 13 ms 6988 KB Output is correct
3 Correct 91 ms 7100 KB Output is correct
4 Correct 162 ms 9436 KB Output is correct
5 Correct 72 ms 9904 KB Output is correct
6 Correct 7 ms 7116 KB Output is correct
7 Correct 7 ms 7116 KB Output is correct
8 Correct 7 ms 6988 KB Output is correct
9 Correct 7 ms 6988 KB Output is correct
10 Correct 8 ms 7116 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8696 KB Output is correct
2 Correct 116 ms 8568 KB Output is correct
3 Correct 56 ms 8544 KB Output is correct
4 Correct 37 ms 8488 KB Output is correct
5 Correct 38 ms 8760 KB Output is correct
6 Correct 34 ms 8688 KB Output is correct
7 Correct 32 ms 8496 KB Output is correct
8 Correct 39 ms 8488 KB Output is correct
9 Correct 38 ms 8484 KB Output is correct
10 Correct 36 ms 8516 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6988 KB Output is correct
2 Correct 13 ms 6988 KB Output is correct
3 Correct 91 ms 7100 KB Output is correct
4 Correct 162 ms 9436 KB Output is correct
5 Correct 72 ms 9904 KB Output is correct
6 Correct 7 ms 7116 KB Output is correct
7 Correct 7 ms 7116 KB Output is correct
8 Correct 7 ms 6988 KB Output is correct
9 Correct 7 ms 6988 KB Output is correct
10 Correct 8 ms 7116 KB Output is correct
11 Correct 44 ms 8696 KB Output is correct
12 Correct 116 ms 8568 KB Output is correct
13 Correct 56 ms 8544 KB Output is correct
14 Correct 37 ms 8488 KB Output is correct
15 Correct 38 ms 8760 KB Output is correct
16 Correct 34 ms 8688 KB Output is correct
17 Correct 32 ms 8496 KB Output is correct
18 Correct 39 ms 8488 KB Output is correct
19 Correct 38 ms 8484 KB Output is correct
20 Correct 36 ms 8516 KB Output is correct
21 Correct 43 ms 8616 KB Output is correct
22 Correct 118 ms 8584 KB Output is correct
23 Correct 1089 ms 8744 KB Output is correct
24 Correct 1975 ms 11048 KB Output is correct
25 Correct 255 ms 11332 KB Output is correct
26 Correct 181 ms 12004 KB Output is correct
27 Correct 44 ms 9924 KB Output is correct
28 Correct 46 ms 9868 KB Output is correct
29 Correct 141 ms 20744 KB Output is correct
30 Correct 1292 ms 13252 KB Output is correct
31 Correct 122 ms 13792 KB Output is correct
32 Correct 123 ms 14432 KB Output is correct
33 Correct 2187 ms 13520 KB Output is correct
34 Correct 136 ms 13764 KB Output is correct
35 Correct 123 ms 14600 KB Output is correct
36 Correct 133 ms 13424 KB Output is correct
37 Correct 143 ms 13816 KB Output is correct
38 Correct 521 ms 22244 KB Output is correct
39 Correct 1669 ms 17484 KB Output is correct
40 Correct 2113 ms 13408 KB Output is correct
41 Correct 155 ms 22324 KB Output is correct
42 Correct 151 ms 22284 KB Output is correct
43 Correct 208 ms 22404 KB Output is correct
44 Execution timed out 4094 ms 10108 KB Time limit exceeded
45 Halted 0 ms 0 KB -