QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#864010 | #9163. Text editor | fryan | 5 | 1ms | 8040kb | C++20 | 2.8kb | 2025-01-20 07:17:48 | 2025-01-20 07:17:49 |
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long
namespace static_rmq {
//see yosupo for usage details
const int K = 19;
const int mxn = 5e5+5;
int N;
int st[K+1][mxn];
void build() {
for (int i=1; i<=K; i++)
for (int j=0; j+(1<<i)<=N; j++)
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
void init(int* arr, int size) {
copy(arr,arr+size,st[0]);
N = size;
build();
}
int query(int l, int r) {
int i=log2(r-l+1);
return min(st[i][l],st[i][r-(1<<i)+1]);
}
};
const int mxn = 1e6+5;
const int inf = 1e18;
int n,l[mxn],sl,sc,el,ec;
int ans = inf;
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> dij;
map<array<int,2>,int> memo;
int r_search(int l, int r, int v, int p) {
if (l==r) return r;
if (l+1==r) {
if (static_rmq::query(r,p-1) < v) return r;
return l;
}
int m = (l+r)/2;
if (static_rmq::query(m,p-1) < v) {
return r_search(m,r,v,p);
}
return r_search(l,r,v,p);
}
int l_search(int l, int r, int v, int p) {
if (l==r) return r;
if (l+1==r) {
if (static_rmq::query(p+1,l) < v) return l;
return r;
}
int m = (l+r)/2;
if (static_rmq::query(p+1,m) < v) {
return l_search(l,m,v,p);
}
return l_search(m,r,v,p);
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>sl>>sc>>el>>ec;
for (int i=1; i<=n; i++) {
cin>>l[i];
}
l[0] = l[n+1] = -1;
static_rmq::init(l,n+1);
dij.push({0,sl,sc});
while (sz(dij)) {
auto [d,x,y] = dij.top(); dij.pop();
if (d >= ans) break;
if (memo.count({x,y}) && memo[{x,y}] <= d) continue;
// cout<<x<<" "<<y<<" "<<d<<"\n";
memo[{x,y}] = d;
if (x == el) {
ans = min(ans,d+abs(y-ec));
}
//case 1 - go to bottom of current
dij.push({d+y-1,x,1});
//case 2 - go to top of current
dij.push({d+l[x]+1-y,x,l[x]+1});
//case 3 - go to first of next by going up
if (x<n) {
dij.push({d+l[x]+2-y,x+1,1});
}
//case 4 - go to last of before by going down
if (x>1) {
dij.push({d+y,x-1,l[x-1]+1});
}
//case 5 - go to next if at bottom
if (y==1) {
if (x>1) dij.push({d+1,x-1,1});
if (x<n) dij.push({d+1,x+1,1});
}
//case 6 - go to next lowest if not at bottom
if (y > 1) {
int f = r_search(0,x-1,y,x);
// cout<<f<<endl;
if (f != 0) {
dij.push({d+x-f,f,l[f]+1});
}
f = l_search(x+1,n+1,y,x);
if (f != n+1) {
dij.push({d+f-x,f,l[f]+1});
}
}
//case 7 - go directly to end
if (x > el) {
int ny = min(y,static_rmq::query(el,x)+1);
dij.push({d+x-el,el,ny});
} else if (x < el) {
int ny = min(y,static_rmq::query(x,el)+1);
dij.push({d+el-x,el,ny});
}
}
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 7904kb
input:
1 1 1 1 1 0
output:
0
result:
ok single line: '0'
Test #2:
score: 5
Accepted
time: 0ms
memory: 8040kb
input:
2 1 1 1 500000001 1000000000 0
output:
500000000
result:
ok single line: '500000000'
Test #3:
score: 5
Accepted
time: 0ms
memory: 8040kb
input:
2 1 429578866 1 327150572 584071526 0
output:
102428294
result:
ok single line: '102428294'
Test #4:
score: 5
Accepted
time: 0ms
memory: 7908kb
input:
2 2 1 2 1 929403468 0
output:
0
result:
ok single line: '0'
Test #5:
score: 5
Accepted
time: 1ms
memory: 7908kb
input:
2 2 1 2 1 989240738 0
output:
0
result:
ok single line: '0'
Test #6:
score: 5
Accepted
time: 0ms
memory: 8032kb
input:
2 2 1 1 371562870 436620826 0
output:
65057958
result:
ok single line: '65057958'
Test #7:
score: 5
Accepted
time: 0ms
memory: 8040kb
input:
2 1 103853165 1 705401000 836091409 0
output:
130690412
result:
ok single line: '130690412'
Test #8:
score: 5
Accepted
time: 0ms
memory: 7908kb
input:
2 2 1 2 1 924491619 0
output:
0
result:
ok single line: '0'
Subtask #2:
score: 0
Time Limit Exceeded
Test #9:
score: 0
Time Limit Exceeded
input:
952 212 33 98 130 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 1312 13...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #43:
score: 0
Time Limit Exceeded
input:
878478 323624 9772968 215921 1051399 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227925538 227...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%