| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 60422 |
2018-07-24T07:25:59 Z |
ainta(#1738) |
Railway Trip (JOI17_railway_trip) |
C++11 |
|
2000 ms |
69956 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define N_ 101000
#define pii pair<int,int>
using namespace std;
int n, K, Q, w[N_], Num[N_], par[N_][20], pL[N_][20], res;
vector<int>G[N_], E[N_], L[N_];
set<int>Set;
int Lp[N_][20], LL[N_][20], Rp[N_][20], RL[N_][20];
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_];
struct point {
int a, dep;
bool operator<(const point &p)const {
return dep < p.dep;
}
};
vector<point>T1, T2;
void DFS(int a) {
if (cnt & 1) T1.push_back({ a,w[a] });
else T2.push_back({ a,w[a] });
v[a] = cnt;
for (auto &x : E[a]) {
if (v[x] != cnt)DFS(x);
}
}
void Go(int a) {
if (E[a].size() == 0)return;
if (E[a].size() == 1) {
par[a][0] = E[a][0];
pL[a][0] = L[a][0];
return;
}
Lp[a][0] = E[a][0], LL[a][0] = L[a][0];
Rp[a][0] = E[a][1], RL[a][0] = L[a][1];
int b = E[a][0], e = E[a][1], r = L[a][0];
while (1) {
if (w[b] < w[e]) {
par[a][0] = e;
pL[a][0] = r;
return;
}
if (w[b] > w[e]) {
par[a][0] = b;
pL[a][0] = r;
return;
}
if (E[b].empty() && E[e].empty())return;
if (L[b][0] != L[e][0]) {
if (L[b][0] < L[e][0]) {
par[a][0] = E[b][0];
pL[a][0] = r + L[b][0];
}
else {
par[a][0] = E[e][0];
pL[a][0] = r + L[e][0];
}
return;
}
b = E[b][0], e = E[e][0];
}
}
pii tL;
pii Get(int a, int h) {
int l = a, r = a;
tL = { 0,0 };
for (int i = 17; i >= 0; i--) {
if (Lp[l][i] && w[Lp[l][i]] <= h) {
tL.first += LL[l][i];
l = Lp[l][i];
}
if (Rp[r][i] && w[Rp[r][i]] <= h) {
tL.second += RL[r][i];
r = Rp[r][i];
}
}
return { l,r };
}
void UDT(int a, int b, int l1, int l2) {
if (w[a] == w[b]) {
res = min(res, abs(Num[a] - Num[b]) + l1 + l2);
}
}
bool Do(int h, int a, int b){
if (w[a] > h || w[b] > h)return false;
int L1 = 0, L2 = 0;
for (int i = 17; i >= 0; i--) {
if (par[a][i] && w[par[a][i]] <= h) {
L1 += pL[a][i];
a = par[a][i];
}
if (par[b][i] && w[par[b][i]] <= h) {
L2 += pL[b][i];
b = par[b][i];
}
}
pii t1 = Get(a, h);
pii tL1 = tL;
pii t2 = Get(b, h);
pii tL2 = tL;
tL1.first += L1, tL1.second += L1;
tL2.first += L2, tL2.second += L2;
UDT(t1.first, t2.first, tL1.first, tL2.first);
UDT(t1.first, t2.second, tL1.first, tL2.second);
UDT(t1.second, t2.first, tL1.second, tL2.first);
UDT(t1.second, t2.second, tL1.second, tL2.second);
if (t1.first == t2.first)return true;
if (t1.first == t2.second)return true;
if (t1.second == t2.first)return true;
if (t1.second == t2.second)return true;
return false;
}
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);
}
}
for (i = 1; i <= n; i++) {
Go(i);
}
int j;
for (i = 0; i < 18; i++) {
for (j = 1; j <= n; j++) {
par[j][i + 1] = par[par[j][i]][i];
pL[j][i + 1] = pL[par[j][i]][i] + pL[j][i];
Lp[j][i + 1] = Lp[Lp[j][i]][i];
LL[j][i + 1] = LL[Lp[j][i]][i] + LL[j][i];
Rp[j][i + 1] = Rp[Rp[j][i]][i];
RL[j][i + 1] = RL[Rp[j][i]][i] + RL[j][i];
}
}
while (Q--) {
int x, y;
scanf("%d%d", &x, &y);
int b = 1, e = K, mid;
res = 1e9;
/* while (b <= e) {
mid = (b + e) >> 1;
if (Do(mid, x,y))e = mid - 1;
else b = mid + 1;
}*/
for (int i = 1; i <= K; i++)Do(i, x, y);
printf("%d\n", res-1);
}
}
Compilation message
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:145: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &w[i]);
~~~~~^~~~~~~~~~~~~
railway_trip.cpp:201:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
8292 KB |
Output is correct |
| 2 |
Incorrect |
296 ms |
67772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
745 ms |
68460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2043 ms |
69956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
