oj.uz

Submission #334366

# Submission time Handle Problem Language Result Execution time Memory
334366 2020-12-09T05:08:43 Z CodeTiger927 ČVENK (COI15_cvenk) C++14
100 / 100
 253 ms 123116 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")


using namespace std;

#include <iostream>
#include <algorithm>

#define MAXN 100005

struct node {
	node* c[2];
	long long x,y,s,xy;
	node(long long _x,long long _y): x(_x),y(_y),xy(_x + _y),s(0) {
		c[0] = c[1] = nullptr;
	}
	node* insert(node* next,bool lr) {
		s++;
		if(!c[lr]) c[lr] = next;
		if(next -> x < c[lr] -> x || next -> y < c[lr] -> y) {
			next -> c[lr] = c[lr];
			next -> s += c[lr] -> s;
			c[lr] = next;
			return next;
		}
		if(next -> x > c[lr] -> x || next -> y > c[lr] -> y) {
			return c[lr] -> insert(next,lr);
		}
		return c[lr];
	}
};

node* root = new node(0,0);
long long sum,ans;
long long N;
pair<long long,long long> pts[MAXN];

void dfs(node* cur,long long curN) {
	ans = min(ans,curN);
	if(cur -> c[0]) dfs(cur -> c[0],curN + (1ll * N - 2 * cur -> c[0] -> s) * (cur -> c[0] -> xy - cur -> xy));
	if(cur -> c[1]) dfs(cur -> c[1],curN + (1ll * N - 2 * cur -> c[1] -> s) * (cur -> c[1] -> xy - cur -> xy));
}

int main() {
	cin >> N;
	for(int i = 0;i < N;++i) {
		cin >> pts[i].first >> pts[i].second;
		sum += pts[i].first + pts[i].second;
	}
	sort(pts,pts + N,[&](pair<long long,long long> p1,pair<long long,long long> p2) {return (p1.first + p1.second) > (p2.first + p2.second);});
	for(int i = 0;i < N;++i) {
		long long curX,curY;
		curX = curY = 0;
		node* cur = root;
		for(int j = 29;j >= 0;--j) {
			if(pts[i].first & (1 << j)) {
				curX += (1 << j);
				cur = cur -> insert(new node(curX,curY),0);
			}else if(pts[i].second & (1 << j)) {
				curY += (1 << j);
				cur = cur -> insert(new node(curX,curY),1);
			}
		}
		cur -> s++;
	}
	ans = sum;
	dfs(root,sum);
	cout << ans << endl;
	return 0;
}

Compilation message

cvenk.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("Ofast")
      | 
cvenk.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
cvenk.cpp: In constructor 'node::node(long long int, long long int)':
cvenk.cpp:15:18: warning: 'node::xy' will be initialized after [-Wreorder]
   15 |  long long x,y,s,xy;
      |                  ^~
cvenk.cpp:15:16: warning:   'long long int node::s' [-Wreorder]
   15 |  long long x,y,s,xy;
      |                ^
cvenk.cpp:16:2: warning:   when initialized here [-Wreorder]
   16 |  node(long long _x,long long _y): x(_x),y(_y),xy(_x + _y),s(0) {
      |  ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 35308 KB Output is correct
2 Correct 86 ms 35308 KB Output is correct
3 Correct 69 ms 23532 KB Output is correct
4 Correct 66 ms 21740 KB Output is correct
5 Correct 70 ms 23788 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 123116 KB Output is correct
2 Correct 253 ms 122988 KB Output is correct
3 Correct 231 ms 107116 KB Output is correct
4 Correct 199 ms 98796 KB Output is correct
5 Correct 200 ms 97644 KB Output is correct