Submission #60403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60403	2018-07-24T06:02:33 Z	ainta(#1738)	Park (JOI17_park)	C++11	Compilation error	0 ms	0 KB

park

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define N_ 101000
using namespace std;
int n, K, Q, w[N_], Num[N_];
vector<int>G[N_], E[N_], L[N_];
set<int>Set;
int BIT[N_][2];
int D1[N_], D2[N_];
void Add(int a, int ck, int b) {
	while (a <= n) {
		BIT[a][ck] += b;
		a += (a&-a);
	}
}
int Sum(int a, int ck) {
	int r = 0;
	while (a) {
		r += BIT[a][ck];
		a -= (a&-a);
	}
	return r;
}

void Add_Edge(int a, int b, int d) {
	E[a].push_back(b);
	L[a].push_back(d);
}

int cnt, v[N_];
vector<int>T1, T2;

void Put(int a) {
	v[a] = cnt;
	if (cnt & 1)T1.push_back(a);
	else T2.push_back(a);
}

void Go(int a) {
	Put(a);
	while (1) {
		if (E[a].size() != 1)break;
		a = E[a][0];
		Put(a);
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int i;
	scanf("%d%d%d", &n, &K, &Q);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		D1[i] = D2[i] = 1e9;
		G[w[i]].push_back(i);
	}
	for (i = K; i >= 1; i--) {
		if (G[i].empty())continue;
		for (auto &t : G[i]) {
			Add(t, 0, 1);
			Add(t, 1, 1);
		}
		if (!Set.empty()) {
			for (auto &t : G[i]) {
				auto it = Set.lower_bound(t);
				int d1 = 1e9, d2 = 1e9, l, r;
				if (it != Set.end()) {
					d2 = Sum(*it, 0) - Sum(t, 0) + 1;
					r = *it;
				}
				if (it != Set.begin()) {
					it--;
					d1 = Sum(t, 0) - Sum(*it, 0);
					l = *it;
				}
				int M = min(d1, d2);
				if (d1 == M) {
					Add_Edge(t, l, d1);
				}
				if (d2 == M) {
					Add_Edge(t, r, d2);
				}
			}
		}
		for (auto &t : G[i]) {
			Set.insert(t);
			Num[t] = Sum(t, 1);
			Add(t, 0, -1);
		}
	}
	while (Q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		T1.clear();
		T2.clear();
		cnt++;
		Go(a);
		cnt++;
		Go(b);
		D1[a] = 0;
		for (auto &t : T1) {
			int x = t;
			for (i = 0; i < E[x].size(); i++) {
				D1[E[x][i]] = min(D1[E[x][i]], D1[x] + L[x][i]);
			}
		}
		D2[b] = 0;
		for (auto &t : T2) {
			int x = t;
			for (i = 0; i < E[x].size(); i++) {
				D2[E[x][i]] = min(D2[E[x][i]], D2[x] + L[x][i]);
			}
		}
		int res = 1e9;
		int pv = 0;
		for (i = 0; i < T1.size(); i++) {
			while (pv < T2.size() && w[T2[pv]] < w[T1[i]])pv++;
			for (int ii = i; ii < T1.size() && w[T1[ii]] == w[T1[i]]; ii++) {
				for (int jj = pv; jj < T2.size() && w[T2[jj]] == w[T1[i]]; jj++) {
					res = min(res, D1[T1[ii]] + D2[T2[jj]] + abs(Num[T1[ii]] - Num[T2[jj]]));
				}
			}
		}
		for (auto &x : T1)D1[x] = 1e9;
		for (auto &x : T2)D2[x] = 1e9;
		printf("%d\n", res-1);
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (i = 0; i < E[x].size(); i++) {
                ~~^~~~~~~~~~~~~
park.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (i = 0; i < E[x].size(); i++) {
                ~~^~~~~~~~~~~~~
park.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < T1.size(); i++) {
               ~~^~~~~~~~~~~
park.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (pv < T2.size() && w[T2[pv]] < w[T1[i]])pv++;
           ~~~^~~~~~~~~~~
park.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int ii = i; ii < T1.size() && w[T1[ii]] == w[T1[i]]; ii++) {
                     ~~~^~~~~~~~~~~
park.cpp:122:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int jj = pv; jj < T2.size() && w[T2[jj]] == w[T1[i]]; jj++) {
                       ~~~^~~~~~~~~~~
park.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &K, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~
park.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
park.cpp:69:32: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int d1 = 1e9, d2 = 1e9, l, r;
                                ^
park.cpp:69:29: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int d1 = 1e9, d2 = 1e9, l, r;
                             ^
/tmp/ccAMosFG.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccrj7QZb.o:park.cpp:(.text.startup+0x0): first defined here
/tmp/ccAMosFG.o: In function `main':
grader.cpp:(.text.startup+0x17a): undefined reference to `Detect(int, int)'
collect2: error: ld returned 1 exit status