Submission #1092903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092903		Sunbae	Best Place (NOI17_bestplace)	C++17	3 / 100	99 ms	6856 KiB

bestplace

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
ll bit[4][N], p[2];
int x[N], y[N], cp[2][N], m[2], A[2];
void upd(int j, int i, ll v){ for(; i<=m[j/2]; i+=i&-i) bit[j][i] += v;}
ll qry(int j, int i){ ll r = 0; for(; i; i-=i&-i) r += bit[j][i]; return r;}
int pos(int j, int x){ return upper_bound(cp[j], cp[j] + m[j], x) - cp[j];}
signed main(){	
	int n; scanf("%d", &n);
	for(int i = 0; i<n; ++i){
		scanf("%d %d", x+i, y+i);
		cp[0][m[0]++] = x[i]; cp[1][m[1]++] = y[i];
	}
	for(int j = 0; j<2; ++j) sort(cp[j], cp[j]+m[j]), m[j] = unique(cp[j], cp[j]+m[j]) - cp[j];
	for(int i = 0; i<n; ++i){
		int X = pos(0, x[i]), Y = pos(1, y[i]);
		upd(0, X, +1); upd(1, X, +x[i]);
		upd(2, Y, +1); upd(3, Y, +y[i]);
	}
	ll mn = LLONG_MAX;
	for(int i = 0; i<n; ++i){
		int X = pos(0, x[i]), Y = pos(1, y[i]);
		upd(0, X, -1); upd(1, X, -x[i]);
		upd(2, Y, -1); upd(3, Y, -y[i ]);
		p[0] = qry(0, X) * x[i] - qry(1, X) + (qry(1, m[0]) - qry(0, X)) - (qry(0, m[0]) - qry(0, X)) * x[i];
		p[1] = qry(2, X) * y[i] - qry(3, X) + (qry(3, m[1]) - qry(3, X)) - (qry(2, m[1]) - qry(2, X)) * y[i];
		if(p[0] + p[1] < mn){
			A[0] = x[i]; A[1] = y[i];
			mn = p[0] + p[1];
		}
		upd(0, X, +1); upd(1, X, +x[i]);
		upd(2, Y, +1); upd(3, Y, +y[i]);
	}
	printf("%d %d", A[0], A[1]);
}

Compilation message (stderr)

bestplace.cpp: In function 'int main()':
bestplace.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
bestplace.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d %d", x+i, y+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 0 / 20
• Subtask 3: 0 / 28
• Subtask 4: 0 / 13
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19