oj.uz

Submission #521772

# Submission time Handle Problem Language Result Execution time Memory
521772 2022-02-03T03:42:29 Z amunduzbaev IOI Fever (JOI21_fever) C++14
0 / 100
 170 ms 164932 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 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 164932 KB Output is correct
2 Correct 146 ms 164820 KB Output is correct
3 Correct 146 ms 164932 KB Output is correct
4 Correct 170 ms 164800 KB Output is correct
5 Correct 148 ms 164900 KB Output is correct
6 Correct 149 ms 164760 KB Output is correct
7 Correct 146 ms 164864 KB Output is correct
8 Incorrect 149 ms 164932 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 164836 KB Output is correct
2 Correct 148 ms 164724 KB Output is correct
3 Correct 145 ms 164804 KB Output is correct
4 Correct 146 ms 164804 KB Output is correct
5 Correct 151 ms 164784 KB Output is correct
6 Correct 144 ms 164828 KB Output is correct
7 Correct 142 ms 164680 KB Output is correct
8 Correct 145 ms 164848 KB Output is correct
9 Correct 148 ms 164776 KB Output is correct
10 Correct 147 ms 164808 KB Output is correct
11 Correct 144 ms 164804 KB Output is correct
12 Correct 143 ms 164676 KB Output is correct
13 Correct 154 ms 164768 KB Output is correct
14 Correct 144 ms 164780 KB Output is correct
15 Correct 145 ms 164708 KB Output is correct
16 Correct 146 ms 164712 KB Output is correct
17 Correct 149 ms 164716 KB Output is correct
18 Correct 145 ms 164800 KB Output is correct
19 Correct 143 ms 164744 KB Output is correct
20 Correct 146 ms 164784 KB Output is correct
21 Correct 147 ms 164792 KB Output is correct
22 Correct 149 ms 164756 KB Output is correct
23 Correct 149 ms 164780 KB Output is correct
24 Correct 145 ms 164792 KB Output is correct
25 Correct 145 ms 164708 KB Output is correct
26 Correct 156 ms 164692 KB Output is correct
27 Correct 145 ms 164768 KB Output is correct
28 Correct 144 ms 164740 KB Output is correct
29 Correct 146 ms 164756 KB Output is correct
30 Incorrect 152 ms 164808 KB Output isn't correct
31 Halted 0 ms 0 KB -