Submission #1037317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037317		ican0534	Toilets (JOI16_toilets)	C++14	0 / 100	1 ms	2396 KiB

toilets

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct st{int x, ty, gr;} a[200005];
int n, m, g, ans, t[200005];

bool cmpx(st p, st q) {
	if(p.x != q.x) return p.x < q.x;
	return p.ty < q.ty;
}

bool cmpg(st p, st q) {
	if(p.gr != q.gr) return p.gr < q.gr;
	return p.x < q.x;
}

int dist(int *d, int k) {
	int i, s=0, mn;
	for(i=0; i<k-1; i+=2) s += d[i+1] - d[i];
	mn = s;
	if(k%2) {
		for(i=k-2; i>0; i-=2) {
			s += d[i+1] + d[i-1] - 2*d[i];
			mn = min(mn, s);
		}
	}
	return mn;
}

int main() {
	int i, j;
	scanf("%d%d", &n, &m);
	for(i=0; i<n; i++) scanf("%d", &a[i].x), a[i].ty = 1;
	for(i=n; i<n+m; i++) scanf("%d", &a[i].x), a[i].ty = 2;
	sort(a, a+n+m, cmpx);
	for(i=1; i<n+m; i++) {
		if(a[i].ty == a[i-1].ty) {
			a[i].ty==1 ? g-- : g++;
		}
		a[i].gr = g;
	}
	sort(a, a+n+m, cmpg);
	for(i=0; i<n+m; i=j) {
		for(j=i; j<n+m && a[j].gr==a[i].gr; j++) t[j-i] = a[j].x;
		ans += dist(t, j-i);
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

toilets.cpp: In function 'int main()':
toilets.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
toilets.cpp:35:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for(i=0; i<n; i++) scanf("%d", &a[i].x), a[i].ty = 1;
      |                     ~~~~~^~~~~~~~~~~~~~~
toilets.cpp:36:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for(i=n; i<n+m; i++) scanf("%d", &a[i].x), a[i].ty = 2;
      |                       ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 22
• Subtask 3: 0 / 64