oj.uz

Submission #521771

# Submission time Handle Problem Language Result Execution time Memory
521771 2022-02-03T03:41:00 Z amunduzbaev IOI Fever (JOI21_fever) C++14
0 / 100
 167 ms 165020 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++){
		vector<ST> tmp = tree;
		
		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] && ~r[1]){
				for(int j=0;j<8;j++){
					tree[j].sett(pos[j][r[1]], {MAX, -1, -1, -1});
				}
			}
			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;
		}
		swap(tmp, tree);
		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

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 164928 KB Output is correct
2 Correct 153 ms 164824 KB Output is correct
3 Correct 153 ms 164792 KB Output is correct
4 Correct 150 ms 164824 KB Output is correct
5 Correct 152 ms 164892 KB Output is correct
6 Correct 151 ms 164808 KB Output is correct
7 Correct 152 ms 164804 KB Output is correct
8 Incorrect 151 ms 164904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 164784 KB Output is correct
2 Correct 150 ms 164736 KB Output is correct
3 Correct 147 ms 164796 KB Output is correct
4 Correct 160 ms 164704 KB Output is correct
5 Correct 150 ms 164728 KB Output is correct
6 Correct 149 ms 164688 KB Output is correct
7 Correct 152 ms 164820 KB Output is correct
8 Correct 149 ms 164740 KB Output is correct
9 Correct 148 ms 164780 KB Output is correct
10 Correct 149 ms 164728 KB Output is correct
11 Correct 149 ms 164684 KB Output is correct
12 Correct 150 ms 164916 KB Output is correct
13 Correct 151 ms 164804 KB Output is correct
14 Correct 149 ms 164756 KB Output is correct
15 Correct 150 ms 164804 KB Output is correct
16 Correct 154 ms 164716 KB Output is correct
17 Correct 149 ms 164676 KB Output is correct
18 Correct 148 ms 164740 KB Output is correct
19 Correct 150 ms 164892 KB Output is correct
20 Correct 159 ms 165020 KB Output is correct
21 Correct 151 ms 164804 KB Output is correct
22 Correct 150 ms 164744 KB Output is correct
23 Correct 167 ms 164796 KB Output is correct
24 Correct 159 ms 164804 KB Output is correct
25 Correct 148 ms 164764 KB Output is correct
26 Correct 148 ms 164756 KB Output is correct
27 Correct 148 ms 164804 KB Output is correct
28 Correct 154 ms 164888 KB Output is correct
29 Correct 148 ms 164732 KB Output is correct
30 Incorrect 148 ms 164708 KB Output isn't correct
31 Halted 0 ms 0 KB -