#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000,DECA=(1<<17);
int nbVal,typeMaxi,nbReq;
int val[TAILLE_MAX];
vector<int> posVal[TAILLE_MAX];
set<int> plusGrand;
set<int>::iterator it;
int supVois[TAILLE_MAX][2];
int distVois[TAILLE_MAX][2];
int numEgau[TAILLE_MAX];
int arbreSom[2*DECA];
int voisGau[TAILLE_MAX][2],voisDro[TAILLE_MAX][2];
int distGau[TAILLE_MAX][2],distDro[TAILLE_MAX][2];
void ajout(int pos) {
pos+=DECA;
while (pos>0) {
arbreSom[pos]++;
pos/=2;
}
}
int calcInter(int deb,int fin) {
if (deb==fin) {
return arbreSom[deb];
}
if (deb%2==1) {
return arbreSom[deb]+calcInter(deb+1,fin);
}
if (fin%2==0) {
return arbreSom[fin]+calcInter(deb,fin-1);
}
return calcInter(deb/2,fin/2);
}
void calcSup(int deb,int tab) {
distGau[1][tab]=0;
distDro[1][tab]=0;
voisGau[1][tab]=deb;
voisDro[1][tab]=deb;
int pos;
for (int i=2;i<=typeMaxi;i++) {
pos=voisGau[i-1][tab];
if (val[pos]<i) {
voisGau[i][tab]=supVois[pos][0];
distGau[i][tab]=distGau[i-1][tab]+distVois[pos][0];
}
else {
voisGau[i][tab]=pos;
distGau[i][tab]=distGau[i-1][tab];
}
pos=voisDro[i-1][tab];
if (val[pos]<i) {
voisDro[i][tab]=supVois[pos][1];
distDro[i][tab]=distDro[i-1][tab]+distVois[pos][1];
}
else {
voisDro[i][tab]=pos;
distDro[i][tab]=distDro[i-1][tab];
}
distGau[i][tab]=min(distGau[i][tab],distDro[i][tab]+1);
distDro[i][tab]=min(distDro[i][tab],distGau[i][tab]+1);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbVal>>typeMaxi>>nbReq;
for (int i=1;i<=nbVal;i++) {
cin>>val[i];
numEgau[i]=posVal[val[i]].size();
posVal[val[i]].push_back(i);
}
plusGrand.insert(-INFINI);
plusGrand.insert(INFINI);
for (int i=typeMaxi;i>=1;i--) {
for (int j:posVal[i]) {
it=plusGrand.lower_bound(j);
if (abs((*it))!=INFINI) {
supVois[j][1]=(*it);
}
it--;
if (abs((*it))!=INFINI) {
supVois[j][0]=(*it);
}
}
for (int j:posVal[i]) {
plusGrand.insert(j);
ajout(j);
}
for (int j:posVal[i]) {
if (supVois[j][0]!=0) {
distVois[j][0]=calcInter(DECA+1,DECA+j)-calcInter(DECA+1,DECA+supVois[j][0]);
}
if (supVois[j][1]!=0) {
distVois[j][1]=calcInter(DECA+1,DECA+supVois[j][1])-calcInter(DECA+1,DECA+j);
}
}
}
int deb,fin,rep,hautMax;
for (int ireq=0;ireq<nbReq;ireq++) {
cin>>deb>>fin;
if (deb>fin) {
swap(deb,fin);
}
calcSup(deb,0);
calcSup(fin,1);
hautMax=1;
while (hautMax<=typeMaxi and voisDro[hautMax][0]<=voisGau[hautMax][1]) {
hautMax++;
}
hautMax--;
rep=distDro[hautMax][0]+distGau[hautMax][1]+numEgau[voisGau[hautMax][1]]-numEgau[voisDro[hautMax][0]];
cout<<rep-1<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
15976 KB |
Output is correct |
| 2 |
Incorrect |
78 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2044 ms |
16608 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
