| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 60403 |
2018-07-24T06:02:33 Z |
ainta(#1738) |
Park (JOI17_park) |
C++11 |
|
0 ms |
0 KB |
#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
