oj.uz

Submission #427843

# Submission time Handle Problem Language Result Execution time Memory
427843 2021-06-15T01:22:38 Z amoo_safar IOI Fever (JOI21_fever) C++17
11 / 100
 293 ms 241732 KB 
#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
#define int long long

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int Inf = 1'000'000'010;


int n;
int x[N], y[N];
int dir[N];
pii vec[] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

set< pair<int, int> > st; // time, id
int mk[N];

set<pair<int, int> > vis;

int Collision(int a, int b){
	if(x[a] > x[b]) swap(a, b);
	if(x[a] == x[b]){
		if(y[a] > y[b]) swap(a, b);
		if(dir[a] == 3 && dir[b] == 1)
			return abs(y[a] - y[b]) / 2;
		return Inf;
	}

	if(y[a] == y[b]){
		// if(y[a] > y[b]) swap(a, b);
		if(dir[a] == 0 && dir[b] == 2)
			return abs(x[a] - x[b]) / 2;
		return Inf;
	}

	int dp_a = x[a] + y[a];
	int dp_b = x[b] + y[b];
	int dn_a = x[a] - y[a];
	int dn_b = x[b] - y[b];
	if(dp_a != dp_b && dn_a != dn_b)
		return Inf;
	int d = abs(x[a] - x[b]);
	if(dp_a == dp_b){
		if((dir[a] == 0 && dir[b] == 3) || (dir[a] == 1 && dir[b] == 2))
			return d;
		return Inf;
	} 
	if((dir[a] == 0 && dir[b] == 1) || (dir[a] == 3 && dir[b] == 2))
		return d;
	return Inf;
}

int dis[N];

struct Line {
	int spd = 1, sz;
	vector<pii> Stop, Move;
	vector<pii> ans, mn;
	vector<int> lz;
	void Apply(int id, int x){
		ans[id] = min(ans[id], pii(mn[id].F + x, mn[id].S));
		lz[id] = min(lz[id], x);
	}
	void Shift(int id){
		if(lz[id] != 1)
			Apply(id << 1, lz[id]), Apply(id << 1 | 1, lz[id]);
		lz[id] = 1;
	}
	void Build(int id, int L, int R){
		lz[id] = 1;
		if(L + 1 == R){
			ans[id] = {Inf, Stop[L].S};
			mn[id] = Stop[L];
			return ;
		}
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
		ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}
	void Off(int id, int idx, int L, int R){
		if(L + 1 == R){
			mn[id].F = Inf + Inf;
			ans[id] = mn[id];
			return ;
		}
		int mid = (L + R) >> 1;
		Shift(id);
		if(idx < mid)
			Off(id << 1, idx, L, mid);
		else
			Off(id<<1|1, idx, mid, R);
		ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);	
	}
	void Add(int id, int l, int r, int x, int L, int R){
		if(r <= L || R <= l) return ;
		if(l <= L && R <= r){
			Apply(id, x);
			return ;
		}
		int mid = (L + R) >> 1;
		Shift(id);
		Add(id << 1, l, r, x, L, mid);
		Add(id<<1|1, l, r, x, mid, R);
		ans[id] = min(ans[id << 1], ans[id << 1 | 1]);
		mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
	}

	void Add_Stop(int pos, int id){
		Stop.pb({pos, id});
	}
	void Add_Move(int pos, int id){
		Move.pb({pos, id});
	}
	void Init(){
		sz = Stop.size();
		if(Stop.empty())
			return ;

		for(auto &el : Stop)
			el.F /= spd;
		for(auto &el : Move)
			el.F /= spd;
		sort(all(Stop));

		ans.resize(sz * 4);
		mn.resize(sz * 4);
		lz.resize(sz * 4);
		Build(1, 0, sz);
	}
	void Infect_Move(int pos, int id, int tm){
		// debug(id);
		// debug(tm);
		// for(auto el : Stop){
		// 	int i = el.S;
		// 	// cerr << "&& " << id << ' ' << i << '\n';
		// 	if(el.F < pos + tm) continue;
		// 	if(mk[i]) continue;
		// 	int ds = Collision(id, i);
		// 	assert(ds == el.F - pos);
		// 	if(dis[i] > ds){
		// 		st.erase({dis[i], i});
		// 		dis[i] = ds;
		// 		st.insert({ds, i});
		// 	}
		// }
		// for(auto [_pos, _id] : Stop){
		// 	if(mk[_id]) continue;
		// 	if(pos + tm <= _pos && !mk[_id]){
		// 		assert(Collision(id, _id) == _pos - pos);
		// 		if(dis[_id] > _pos - pos){
		// 			st.erase({dis[_id], _id});
		// 			dis[_id] = _pos - pos;
		// 			st.insert({dis[_id], _id});
		// 		}
		// 	}
		// }

		int idx = lower_bound(all(Stop), pii(pos + tm, -1)) - Stop.begin();
		if(idx == sz)
			return ;
		Add(1, idx, sz, -pos, 0, sz);
		if(dis[ans[1].S] > ans[1].F){
			st.erase({dis[ans[1].S], ans[1].S});
			dis[ans[1].S] = ans[1].F;
			st.insert(ans[1]);
		}
	}
	void Infect_Stop(int pos, int id, int tm){
		int idx = lower_bound(all(Stop), pii(pos, id)) - Stop.begin();
		// assert(idx < sz);
		Off(1, idx, 0, sz);
		if(dis[ans[1].S] > ans[1].F){
			dis[ans[1].S] = ans[1].F;
			st.insert(ans[1]);
		}
	}
	void Reset(){
		Stop.clear();
		Move.clear();
	}
};

Line DIA[4][4][N], U[N], R[N]; 
int CP[N], CN[N], CXX[N], CYY[N];

int rv[4][4], ty[4][4];
void Infect(int u, int tm){
	assert(mk[u] == 0);
	mk[u] = 1;
	// for(int i = 0; i < n; i++){
	// 	if(mk[i]) continue;
	// 	int ds = Collision(u, i);
	// 	if(ds != Inf)
	// 		vis.insert({u, i});

	// 	if(ds >= tm && ds != Inf && dis[i] > ds){
	// 		st.erase({dis[i], i});
	// 		dis[i] = ds;
	// 		st.insert({ds, i});
	// 	}
	// }
	// return ;
	// debug(u);
	int MAX = 1'000'000'000;
	for(int d2 = 0; d2 < 4; d2 ++){
		if((dir[u] + d2) % 2 == 0) continue;
		int pos = rv[dir[u]][d2] ? MAX - x[u] : x[u];
		DIA[dir[u]][d2][ ty[dir[u]][d2] ? CN[u] : CP[u]].Infect_Move(pos, u, tm);
		
		pos = rv[d2][dir[u]] ? MAX - x[u] : x[u];
		DIA[d2][dir[u]][ ty[d2][dir[u]] ? CN[u] : CP[u]].Infect_Stop(pos, u, tm);
	}

}




int Solve(){
	dir[0] = 0;
	for(int i = 1; i < n; i++){
		int X = abs(x[i] - x[0]);
		int Y = abs(y[i] - y[0]);
		if(X == Y){
			if(x[i] < x[0]) dir[i] = 0;
			else dir[i] = y[i] < y[0] ? 3 : 1;
		} else {
			if(X > Y){
				if( x[i] < x[0]) dir[i] = 0;
				else dir[i] = 2;
			} else {
				if( y[i] < y[0]) dir[i] = 3;
				else dir[i] = 1;
			}
		}
	}
	// cerr << "!! " ;
	// for(int i = 0; i < n; i++){
	// 	cerr << dir[i] << ' ';
	// }
	// cerr << '\n';


	// for(int i = 0; i < N; i++) R[i].Reset(), U[i].Reset();
	for(int i = 0; i < 16; i++)
		for(int j = 0; j < N; j++)
			DIA[i >> 2][i & 3][j].Reset();

	// for(int i = 0; i < N; i++) R[i].spd = U[i].spd = 2;

	int MAX = 1'000'000'000;
	for(int i = 0; i < n; i++){
		for(int d2 = 0; d2 < 4; d2 ++){
			if((dir[i] + d2) % 2 == 0) continue;
			
			int pos = rv[dir[i]][d2] ? MAX - x[i] : x[i];
			DIA[dir[i]][d2][ ty[dir[i]][d2] ? CN[i] : CP[i]].Add_Move(pos, i);
			
			pos = rv[d2][dir[i]] ? MAX - x[i] : x[i];
			DIA[d2][dir[i]][ ty[d2][dir[i]] ? CN[i] : CP[i]].Add_Stop(pos, i);
		}
	}
	for(int i = 0; i < 16; i++)
		for(int j = 0; j < N; j++)
			DIA[i >> 2][i & 3][j].Init();

	memset(mk, 0, sizeof mk);
	fill(dis, dis + N, Inf);

	dis[0] = 0;
	st.insert({0, 0});
	while(!st.empty()){
		// cerr << "&&&&&&&\n";
		// for(auto [a1, a2] : st)
		// 	cerr << a1 << ' ' << a2 << '\n';
		// cerr << "-------\n";
		int fr = st.begin() -> S;
		int tm = st.begin() -> F;
		st.erase(st.begin());
		// if(tm > Inf) continue;
		// cerr << "!! " << fr << ' ' << tm << '\n';
		Infect(fr, tm);
	}


	int res = 0;
	for(int i = 0; i < n; i++)
		res += mk[i];
	return res;
}


int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	rv[3][0] = 1; rv[1][0] = 1;
	rv[2][1] = 1; rv[2][3] = 1;

	ty[0][1] = ty[1][0] = ty[2][3] = ty[3][2] = 1;

	cin >> n;
	vector<int> cp, cn, cxx, cyy;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i];
		cp.pb(x[i] + y[i]);
		cn.pb(x[i] - y[i]);
		cxx.pb(x[i]);
		cyy.pb(y[i]);
	}
	sort(all(cp));
	sort(all(cn));
	sort(all(cxx));
	sort(all(cyy));
	for(int i = 0; i < n; i++)
		CP[i] = lower_bound(all(cp), x[i] + y[i]) - cp.begin();
	for(int i = 0; i < n; i++)
		CN[i] = lower_bound(all(cn), x[i] - y[i]) - cn.begin();
	for(int i = 0; i < n; i++)
		CXX[i] = lower_bound(all(cxx), x[i]) - cxx.begin();
	for(int i = 0; i < n; i++)
		CYY[i] = lower_bound(all(cyy), y[i]) - cyy.begin();

	// for(int i = 0; i < n; i++){
	// 	x[i] += x[i];
	// 	y[i] += y[i];
	// }
	
	int ans = 0;
	for(int _ = 0; _ < 4; _++){
		// if(_ == 3)
		ans = max(ans, Solve());
		for(int i = 0; i < n; i++){
			int _x = x[i];
			x[i] = -y[i];
			y[i] = _x;
		}
		for(int i = 0; i < n; i++)
			swap(CP[i], CN[i]);
		// break;
	}
	cout << ans << '\n';
	// for(auto [a1, a2] : vis)
	// 	cerr << "! " << a1 << ' ' << a2 << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct
33 Incorrect 272 ms 241384 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 241572 KB Output is correct
2 Correct 264 ms 241604 KB Output is correct
3 Correct 278 ms 241588 KB Output is correct
4 Correct 276 ms 241524 KB Output is correct
5 Correct 290 ms 241704 KB Output is correct
6 Correct 277 ms 241648 KB Output is correct
7 Correct 268 ms 241732 KB Output is correct
8 Correct 280 ms 241604 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct
33 Incorrect 272 ms 241384 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct
33 Incorrect 272 ms 241384 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct
33 Incorrect 272 ms 241384 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 241452 KB Output is correct
2 Correct 272 ms 241624 KB Output is correct
3 Correct 272 ms 241488 KB Output is correct
4 Correct 259 ms 241444 KB Output is correct
5 Correct 277 ms 241608 KB Output is correct
6 Correct 283 ms 241348 KB Output is correct
7 Correct 274 ms 241452 KB Output is correct
8 Correct 281 ms 241464 KB Output is correct
9 Correct 265 ms 241348 KB Output is correct
10 Correct 265 ms 241348 KB Output is correct
11 Correct 269 ms 241580 KB Output is correct
12 Correct 282 ms 241512 KB Output is correct
13 Correct 273 ms 241560 KB Output is correct
14 Correct 281 ms 241456 KB Output is correct
15 Correct 272 ms 241600 KB Output is correct
16 Correct 286 ms 241540 KB Output is correct
17 Correct 293 ms 241348 KB Output is correct
18 Correct 270 ms 241540 KB Output is correct
19 Correct 281 ms 241404 KB Output is correct
20 Correct 277 ms 241464 KB Output is correct
21 Correct 292 ms 241476 KB Output is correct
22 Correct 276 ms 241456 KB Output is correct
23 Correct 278 ms 241452 KB Output is correct
24 Correct 275 ms 241532 KB Output is correct
25 Correct 275 ms 241372 KB Output is correct
26 Correct 265 ms 241560 KB Output is correct
27 Correct 267 ms 241464 KB Output is correct
28 Correct 287 ms 241628 KB Output is correct
29 Correct 273 ms 241348 KB Output is correct
30 Correct 267 ms 241432 KB Output is correct
31 Correct 282 ms 241660 KB Output is correct
32 Correct 267 ms 241460 KB Output is correct
33 Incorrect 272 ms 241384 KB Output isn't correct
34 Halted 0 ms 0 KB -