oj.uz

답안 #467740

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467740 2021-08-24T09:15:53 Z pure_mem Dragon 2 (JOI17_dragon2) C++14
60 / 100
 1958 ms 20644 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 = 330, 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) {
	BIT.clear();
	int len = gDragon[atk].size();
	for(int i = 1;i <= len;i++)
		tDragon[i] = gDragon[atk][i - 1];
	tAnswer[atk] = 0;		
	for(pair<int, int> v: Query[atk]) {
		if(answer[v.Y] != -1) 
			continue;
		tAnswer[v.X] = 0;	
		for(int i = 0;i < gDragon[v.X].size();i++)
			tDragon[++len] = gDragon[v.X][i];
	}
	sort(tDragon + 1, tDragon + len + 1);

	for(int it = 0;it < 2;it++){
    	for(int i = 1;i <= len;i++) {
    		const Event& cur = dragon[tDragon[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(int i = 1;i <= len;i++) {
   		act[dragon[tDragon[i]].id] = 0;	
   	}
	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();

	vector<int> ord(m);
	for(int i = 0;i < m;i++)
		ord[i] = i + 1;
	sort(ord.begin(), ord.end(), [](int lhs, int rhs){return gDragon[lhs].size() > gDragon[rhs].size();});
	for(int i: ord) {
		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";
}

Compilation message

dragon2.cpp: In function 'void solveHeavy(int)':
dragon2.cpp:238:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |   for(int i = 0;i < gDragon[v.X].size();i++)
      |                 ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6988 KB Output is correct
2 Correct 13 ms 7020 KB Output is correct
3 Correct 86 ms 7108 KB Output is correct
4 Correct 181 ms 9412 KB Output is correct
5 Correct 73 ms 9892 KB Output is correct
6 Correct 7 ms 7128 KB Output is correct
7 Correct 8 ms 7148 KB Output is correct
8 Correct 7 ms 6988 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 6 ms 6988 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 8676 KB Output is correct
2 Correct 121 ms 8568 KB Output is correct
3 Correct 63 ms 8648 KB Output is correct
4 Correct 40 ms 8548 KB Output is correct
5 Correct 40 ms 8900 KB Output is correct
6 Correct 38 ms 8672 KB Output is correct
7 Correct 33 ms 8560 KB Output is correct
8 Correct 40 ms 8456 KB Output is correct
9 Correct 36 ms 8488 KB Output is correct
10 Correct 36 ms 8552 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6988 KB Output is correct
2 Correct 13 ms 7020 KB Output is correct
3 Correct 86 ms 7108 KB Output is correct
4 Correct 181 ms 9412 KB Output is correct
5 Correct 73 ms 9892 KB Output is correct
6 Correct 7 ms 7128 KB Output is correct
7 Correct 8 ms 7148 KB Output is correct
8 Correct 7 ms 6988 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 6 ms 6988 KB Output is correct
11 Correct 45 ms 8676 KB Output is correct
12 Correct 121 ms 8568 KB Output is correct
13 Correct 63 ms 8648 KB Output is correct
14 Correct 40 ms 8548 KB Output is correct
15 Correct 40 ms 8900 KB Output is correct
16 Correct 38 ms 8672 KB Output is correct
17 Correct 33 ms 8560 KB Output is correct
18 Correct 40 ms 8456 KB Output is correct
19 Correct 36 ms 8488 KB Output is correct
20 Correct 36 ms 8552 KB Output is correct
21 Correct 41 ms 8680 KB Output is correct
22 Correct 113 ms 8584 KB Output is correct
23 Correct 1046 ms 8740 KB Output is correct
24 Correct 1958 ms 11056 KB Output is correct
25 Correct 278 ms 11364 KB Output is correct
26 Correct 152 ms 12068 KB Output is correct
27 Correct 46 ms 9984 KB Output is correct
28 Correct 54 ms 10088 KB Output is correct
29 Incorrect 142 ms 20644 KB Output isn't correct
30 Halted 0 ms 0 KB -