oj.uz

답안 #521770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521770 2022-02-03T03:37:10 Z amunduzbaev IOI 바이러스 (JOI21_fever) C++14
0 / 100
 242 ms 165184 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
//~ #define int long long

const int N = 1e5 + 5;
const int MAX = 1e9;
struct node{
	int a, b, p, t;
};

bool operator < (node y, node x){
	if(y.a + y.b == x.a + x.b) return y.a < x.a;
	return y.a + y.b < x.a + x.b;
}

node Min(node a, node b){
	if(a.a < b.a) return a;
	return b;
}

const int M = (1 << 18);

struct ST{
	vector<node> tree, mn;
	vector<int> p[2];
	//~ int p[2][1 << 18];
	
	void init(){
		p[0].resize(M, MAX), p[1].resize(M, -1);
		tree.resize(M), mn.resize(M);
		//~ memset(p[0], 127, sizeof p[0]);
		//~ memset(p[1], -1, sizeof p[1]);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		if((node){mn[x<<1].a, p[0][x]} < tree[x<<1]){
			tree[x<<1] = {mn[x<<1].a, p[0][x], mn[x<<1].p, p[1][x]};
		} 
		if((node){mn[x<<1|1].a, p[0][x]} < tree[x<<1|1]){
			tree[x<<1|1] = {mn[x<<1|1].a, p[0][x], mn[x<<1|1].p, p[1][x]};
		} 
		if(p[0][x<<1] > p[0][x]) p[0][x<<1] = p[0][x], p[1][x<<1] = p[1][x];
		if(p[0][x<<1|1] > p[0][x]) p[0][x<<1|1] = p[0][x], p[1][x<<1|1] = p[1][x];
		p[0][x] = MAX;
		p[1][x] = -1;
	}
	
	void sett(int i, node v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = mn[x] = v; return; }
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		mn[x] = Min(mn[x<<1], mn[x<<1|1]);
	}
	
	void umin(int l, int r, int v, int t, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			if((node){mn[x].a, v} < tree[x]) tree[x] = {mn[x].a, v, mn[x].p, t};
			if(p[0][x] > v){
				p[0][x] = v;
				p[1][x] = t;
			}
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		umin(l, r, v, t, lx, m, x<<1),
		umin(l, r, v, t, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		mn[x] = Min(mn[x<<1], mn[x<<1|1]);
	}
	
	ar<int, 3> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {MAX + MAX, MAX, MAX};
		if(lx >= l && rx <= r) return {tree[x].a + tree[x].b, tree[x].p, tree[x].t};
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
};

ar<int, 2> r[8][N];
int pos[8][N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 2>> p(n);
	for(int i=0;i<n;i++) cin>>p[i][0]>>p[i][1];
	map<int, vector<int>> mm[8];
	for(int i=0;i<n;i++){
		mm[0][p[i][0] - p[i][1]].push_back(i);
		mm[1][p[i][0] - p[i][1]].push_back(i);
		mm[2][p[i][0] + p[i][1]].push_back(i);
		mm[3][p[i][0] + p[i][1]].push_back(i);
		mm[4][p[i][1]].push_back(i);
		mm[5][p[i][1]].push_back(i);
		mm[6][p[i][0]].push_back(i);
		mm[7][p[i][0]].push_back(i);
	}
	
	for(int t=0;t<8;t++){
		int last = 0;
		for(auto& [x, v] : mm[t]){
			sort(v.begin(), v.end(), [&](int i, int j){
				if(t < 6) return p[i][0] < p[j][0];
				return p[i][1] < p[j][1];
			});
			
			for(int i=0;i<(int)v.size();i++){
				r[t][v[i]] = {last, last + (int)v.size() - 1};
				pos[t][v[i]] = last + i;
			} last += v.size();
		}
	}
	
	auto get = [&](int i, int j){
		if(j%2 == 0 && j < 4) return 2 * p[i][0];
		if(j%2 == 1 && j < 4) return -2 * p[i][0];
		if(j == 4) return p[i][0];
		if(j == 5) return -p[i][0];
		if(j == 6) return p[i][1];
		if(j == 7) return -p[i][1];
		assert(0);
	};
	
	vector<ST> tree(8);
	for(int j=0;j<8;j++){
		tree[j].init();
		for(int i=0;i<n;i++){
			tree[j].sett(pos[j][i], {get(i, j), MAX, i, -1});
			//~ cout<<pos[j][i]<<" ";
		}
		
		//~ cout<<endl;
	}
	int ans = 0;
	auto is = [&](int a, int b, int t){
		return (abs(p[a][0] - p[b][0]) + abs(p[a][1] - p[b][1]) >= t);
	};
	
	for(int t=0;t<4;t++){
		ST tmp[8];
		for(int j=0;j<8;j++) tmp[j] = tree[j];
		
		for(int j=0;j<8;j++){
			tree[j].sett(pos[j][0], {get(0, j), -get(0, j), 0, t});
		}
		
		auto find = [&]() -> ar<int, 3>{
			ar<int, 3> r; r[0] = MAX;
			for(int j=0;j<8;j++){
				auto tt = tree[j].get(0, n - 1);
				if(tt[0] < r[0]) r = tt;
			}
			
			if(~r[2]){
				for(int j=0;j<8;j++){
					tree[j].sett(pos[j][r[1]], {MAX, -1, -1, -1});
				}
			}
			//~ cout<<r[0]<<" "<<r[1]<<" "<<r[2]<<endl;
			return r;
		};
		
		int res = 0;
		while(1){
			//~ cout<<"here"<<endl;
			auto u = find();
			
			if(u[1] == -1 || u[2] == -1) break;
			res++;
			
			int i = u[1], t = u[2], tim = u[0];
			//~ cout<<i<<" "<<t<<" "<<tim<<endl;
			{
				auto& v = mm[0][p[i][0] - p[i][1]];
				if(t == 0 || t == 1){
					int lx = pos[0][i] - r[0][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[0][i][0], rx = r[0][i][1];
						tree[0].umin(lx, rx, -2 * p[i][0], (t == 0 ? 3 : 2));
					}
				} else {
					int lx = 0, rx = pos[1][i] - r[1][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m], tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[1][i][0], rx += r[1][i][0];
						tree[1].umin(lx, rx, 2 * p[i][0], (t == 2 ? 1 : 0));
					}
				}
			}
			//~ cout<<"here"<<endl;
			{
				auto& v = mm[2][p[i][0] + p[i][1]];
				if(t == 1 || t == 2){
					int lx = pos[2][i] - r[2][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[2][i][0], rx = r[2][i][1];
						tree[2].umin(lx, rx, -2 * p[i][0], (t == 1 ? 0 : 3));
					}
				} else {
					int lx = 0, rx = pos[3][i] - r[3][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m], tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[3][i][0], rx += r[3][i][0];
						tree[3].umin(lx, rx, 2 * p[i][0], (t == 0 ? 1 : 2));
					}
				}
			}
			//~ cout<<"here"<<endl;
			{
				auto& v = mm[4][p[i][1]];
				if(t == 1){
					int lx = pos[4][i] - r[4][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[4][i][0], rx = r[4][i][1];
						tree[4].umin(lx, rx, -p[i][0], 3);
					}
				} if(t == 3){
					int lx = 0, rx = pos[5][i] - r[5][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m],  tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[5][i][0], rx += r[5][i][0];
						tree[5].umin(lx, rx, p[i][0], 1);
					}
				}
			}
			//~ cout<<"here"<<endl;
			{
				auto& v = mm[6][p[i][0]];
				if(t == 0){
					int lx = pos[6][i] - r[6][i][0], rx = (int)v.size() - 1;
					while(lx < rx){
						int m = (lx + rx) >> 1;
						if(is(i, v[m], tim)) rx = m;
						else lx = m + 1;
					} if(is(i, v[lx], tim)){
						lx += r[6][i][0], rx = r[6][i][1];
						tree[6].umin(lx, rx, -p[i][1], 2);
					}
				} if(t == 2){
					int lx = 0, rx = pos[7][i] - r[7][i][0];
					while(lx < rx){
						int m = (lx + rx + 1) >> 1;
						if(is(i, v[m],  tim)) lx = m;
						else rx = m - 1;
					} if(is(i, v[lx], tim)){
						lx = r[7][i][0], rx += r[7][i][0];
						tree[7].umin(lx, rx, p[i][1], 0);
					}
				}
			}
			
			//~ cout<<"here"<<endl;
		}
		
		//~ cout<<"here"<<endl;
		for(int i=0;i<8;i++) tree[i] = tmp[i];
		ans = max(ans, res);
	}
	
	cout<<ans<<"\n";
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:110:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |   for(auto& [x, v] : mm[t]){
      |             ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 164924 KB Output is correct
2 Correct 211 ms 164892 KB Output is correct
3 Correct 213 ms 164932 KB Output is correct
4 Correct 221 ms 165072 KB Output is correct
5 Correct 226 ms 164892 KB Output is correct
6 Correct 216 ms 164792 KB Output is correct
7 Correct 225 ms 164880 KB Output is correct
8 Incorrect 215 ms 164872 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 164708 KB Output is correct
2 Correct 214 ms 164748 KB Output is correct
3 Correct 214 ms 164800 KB Output is correct
4 Correct 217 ms 164792 KB Output is correct
5 Correct 242 ms 164780 KB Output is correct
6 Correct 212 ms 164720 KB Output is correct
7 Correct 221 ms 164812 KB Output is correct
8 Correct 218 ms 164804 KB Output is correct
9 Correct 216 ms 164776 KB Output is correct
10 Correct 219 ms 164836 KB Output is correct
11 Correct 216 ms 164800 KB Output is correct
12 Correct 215 ms 164804 KB Output is correct
13 Correct 215 ms 164884 KB Output is correct
14 Correct 212 ms 164836 KB Output is correct
15 Correct 210 ms 164796 KB Output is correct
16 Correct 222 ms 164804 KB Output is correct
17 Correct 214 ms 164844 KB Output is correct
18 Correct 212 ms 164760 KB Output is correct
19 Correct 221 ms 164888 KB Output is correct
20 Correct 210 ms 164740 KB Output is correct
21 Correct 212 ms 164808 KB Output is correct
22 Correct 217 ms 164840 KB Output is correct
23 Correct 216 ms 164804 KB Output is correct
24 Correct 216 ms 164832 KB Output is correct
25 Correct 220 ms 164740 KB Output is correct
26 Correct 214 ms 164800 KB Output is correct
27 Correct 214 ms 164788 KB Output is correct
28 Correct 225 ms 165184 KB Output is correct
29 Correct 218 ms 164784 KB Output is correct
30 Incorrect 211 ms 164768 KB Output isn't correct
31 Halted 0 ms 0 KB -