#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
int ar[n];
vector<pair<int, int> > li;
for(int i = 0; i<n; i++){
cin >> ar[i];
}
int left[n];
int dl[n];
dl[0] = 0;
left[0] = 0;
li.push_back(make_pair(ar[0],0));
int cnt[k+1];
int ind[n];
ind[0] = 0;
for(int i = 0; i<=k; i++){
cnt[i] = 0;
}
cnt[ar[0]] = 1;
for(int i= 1; i<n; i++){
ind[i] = cnt[ar[i]];
cnt[ar[i]]++;
while(li[(int)li.size()-1].first<ar[i]){
li.pop_back();
}
if(li[(int)li.size()-1].first==ar[i]){
dl[i] = dl[li[(int)li.size()-1].second]+1;
li.pop_back();
}
else{
dl[i] = 1;
}
if(ar[i]==k){
left[i] = i;
dl[i] = 0;
}
else{
left[i] = li[(int)li.size()-1].second;
}
li.push_back(make_pair(ar[i],i));
}
li.clear();
int right[n];
int dr[n];
dr[n-1] = 0;
right[n-1] = n-1;
li.push_back(make_pair(ar[n-1],n-1));
for(int i = n-2; i>=0; i--){
while(li[(int)li.size()-1].first<ar[i]){
li.pop_back();
}
if(li[(int)li.size()-1].first==ar[i]){
dr[i] = dr[li[(int)li.size()-1].second]+1;
li.pop_back();
}
else{
dr[i] = 1;
}
if(ar[i]==k){
right[i] = i;
dr[i] =0 ;
}
else{
right[i] = li[(int)li.size()-1].second;
}
li.push_back(make_pair(ar[i],i));
}
int dist1[n];
int dist2[n];
bool v1[n];
bool v2[n];
int inf = n+2;
for(int j = 0; j<n; j++){
dist1[j] = inf;
dist2[j] = inf;
v1[j] = false;
v2[j] = false;
}
for(int i = 0; i<q; i++){
int s, t;
cin >> s >> t;
s--;
t--;
vector<int> li1;
dist1[s] = 0;
priority_queue<pair<int, int> > pq1;
pq1.push(make_pair(0,s));
while(pq1.size()>0){
// cout << "Z " << endl;
pair<int, int> now = pq1.top();
// cout << now.first << " " << now.second << endl;
pq1.pop();
if(v1[now.second]){
continue;
}
// cout << "A " << now.second << " " << -now.first << endl;
dist1[now.second] = -now.first;
v1[now.second] = true;
li1.push_back(now.second);
// cout << now.second << " -> " << left[now.second] << endl;
// cout << now.second << " -> R " << right[now.second] << endl;
pq1.push(make_pair(now.first-dl[now.second],left[now.second]));
pq1.push(make_pair(now.first-dr[now.second],right[now.second]));
}
// cout << "X " << endl;
vector<int> li2;
dist2[t] = 0;
priority_queue<pair<int, int> > pq2;
pq2.push(make_pair(0,t));
while(pq2.size()>0){
pair<int, int> now = pq2.top();
pq2.pop();
if(v2[now.second]){
continue;
}
li2.push_back(now.second);
// cout << "B " << now.second << " " << -now.first << endl;
dist2[now.second] = -now.first;
v2[now.second] = true;
pq2.push(make_pair(now.first-dl[now.second],left[now.second]));
pq2.push(make_pair(now.first-dr[now.second],right[now.second]));
}
int ans = inf;
for(int i = 0; i<li1.size(); i++){
for(int j = 0; j<li2.size(); j++){
int a = li1[i];
int b = li2[j];
if(ar[a]==ar[b]){
if(ar[a]==k || left[b]<a){
int best = ind[a]-ind[b];
if(best<0){
best = -best;
}
int here = dist1[a]+dist2[b]+best-1;
// cout << a << " " << b << " # " << here << endl;
// cout << "OK " << dist1[a] << " " << dist2[b] << " " << best << " " << cnt[ar[a]]-best << endl;
ans = min(here,ans);
}
}
}
}
for(int i = 0; i<li1.size(); i++){
int x = li1[i];
v1[x] = false;
dist1[x] = inf;
}
for(int i = 0; i<li2.size(); i++){
int x = li2[i];
v2[x] = false;
dist2[x] = inf;
}
cout << ans << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
620 ms |
5424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1200 ms |
5576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
