Submission #1315796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315796		Zbyszek99	Text editor (CEOI24_editor)	C++20	100 / 100	763 ms	28200 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int n;
int arr[1000001];
int dist1[1000001];
int dist2[1000001];

void calc_zero_dist1(int r, int c)
{
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    int cur_min = c;
    for(int i = r; i >= 1; i--)
    {
        cur_min = min(cur_min,arr[i]);
        pq.push({r-i+cur_min,i});
        if(i != n) pq.push({r-i+arr[i]-cur_min+1,i+1});
    }
    cur_min = c;
    rep2(i,r,n)
    {
        cur_min = min(cur_min,arr[i]);
        pq.push({i-r+cur_min,i});
        if(i != n) pq.push({i-r+arr[i]-cur_min+1,i+1});
    }
    rep2(i,1,n) dist1[i] = 1e9;
    while(!pq.empty())
    {
        pii t = pq.top();
        pq.pop();
        if(dist1[t.ss] != 1e9) continue;
        dist1[t.ss] = t.ff;
        if(t.ss != 1) pq.push({t.ff+1,t.ss-1});
        if(t.ss != n) pq.push({t.ff+1,t.ss+1});
    }
}

void calc_zero_dist2(int r, int c)
{
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({c,r});
    int cur_min = 1e9;
    for(int i = r; i >= 1; i--)
    {
        cur_min = min(cur_min,arr[i]);
        if(i != n) pq.push({abs(i-r)+abs(c-cur_min)+1,i+1});
    }
    cur_min = 1e9;
    rep2(i,r,n)
    {
        cur_min = min(cur_min,arr[i]);
        if(i != n) pq.push({abs(i-r)+abs(c-cur_min)+1,i+1});
    }
    rep2(i,1,n) dist2[i] = 1e9;
    while(!pq.empty())
    {
        pii t = pq.top();
        pq.pop();
        if(dist2[t.ss] != 1e9) continue;
        dist2[t.ss] = t.ff;
        if(t.ss != 1) pq.push({t.ff+1,t.ss-1});
        if(t.ss != n) pq.push({t.ff+1,t.ss+1});
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n;
    int r1,c1;
    int r2,c2;
    cin >> r1 >> c1 >> r2 >> c2;
    c1--;
    c2--;
    rep2(i,1,n) cin >> arr[i];
    calc_zero_dist1(r1,c1);
    calc_zero_dist2(r2,c2);
    int ans = 1e9;
    rep2(i,1,n) ans = min(ans,dist1[i]+dist2[i]);
    int min_b = c1;
    rep2(i,min(r1,r2),max(r1,r2)) min_b = min(min_b,arr[i]);
    int cur_min = min_b;
    for(int i = r1; i >= 1; i--)
    {
        cur_min = min(cur_min,arr[i]);
        ans = min(ans,abs(i-r1)+abs(i-r2)+abs(c2-cur_min));
    }
    cur_min = min_b;
    rep2(i,r1,n)
    {
        cur_min = min(cur_min,arr[i]);
        ans = min(ans,abs(i-r1)+abs(i-r2)+abs(c2-cur_min));
    }
    cout << ans << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 26 / 26
• Subtask 4: 11 / 11
• Subtask 5: 44 / 44