Submission #1220497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220497		KindaGoodGames	Text editor (CEOI24_editor)	C++20	5 / 100	4102 ms	396292 KiB

Main

// #pragma GCC optimize("O3, unroll-loops, Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>

using namespace std;
// #define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max()/2;
const int MAXIT = 25000000;

struct cvec{
    vector<int> v;
    int n;
    int m;

    cvec(int n, int m, int init){
        this->n = n;
        this->m = m;
        v.resize(n*m, init);
    }

    int get(int i, int j){
        return v[(i*m)+j];
    }
    void set(int i, int j, int d){
        v[(i*m)+j] = d;
    }
};

struct cvecp{
    vector<pii> v;
    int n;
    int m;

    cvecp(int n, int m, pii init){
        this->n = n;
        this->m = m;
        v.resize(n*m, init);
    }

    pii get(int i, int j){
        return v[(i*m)+j];
    }
    void set(int i, int j, pii d){
        v[(i*m)+j] = d;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int sr, sc;
    int er, ec;
    
    cin >> n;
    cin >> sr >> sc;
    cin >> er >> ec;

    sr--;sc--;
    er--;ec--;
 

    vector<int> arr(n);

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    
    set<int> important;

    for(int i = 0; i < n; i++){
        important.insert(arr[i]);
    }
    important.insert(sc);
    important.insert(ec);
    important.insert(INF);
    important.insert(-INF);

    vector<int> pos(important.begin(),important.end()); 
    map<int,int> toInd;
    for(int i = 0; i < pos.size(); i++){
        toInd[pos[i]] = i;
    }
     
    priority_queue<tiii,vector<tiii>, greater<tiii>> pq; 
    cvec dist(n, pos.size(), INF);   

    
    pq.push({0,sr,sc});

    int iter = 0;
    int cand = INF;
    while(pq.size()){
        iter++;
        int d,r,c;
        tie(d,r,c) = pq.top(); pq.pop();

        int indC =toInd[c];
        
        if(iter >= MAXIT) break;
        if(dist.get(r,indC) < d) continue;
        dist.set(r,indC,d);

        if(r == er && ec == c) break; 

        int nxt = pos[indC+1];
        int prev = pos[indC-1];

        auto psh = [&](int D, int R, int C){
            if(dist.get(R,toInd[C]) <= D) {
                return;
            }
            int a = 0;
            if(er > R){
                a = er-R;
            }else{
                a = R-er;
            }
            int ad = 0;
            if(er != C) ad = 1;
            if(D+a+ad >= cand) return;
            if(R == er && C == ec){
                cand = D;
                dist.set(er,toInd[ec],D); 
            }
            
            if(iter >= MAXIT) return;
            pq.push({D,R,C});
        };

        // horizontal
        if(prev >= 0) psh(c-prev+d,r,prev);
        else if(r-1 >= 0){
            psh(d+1,r-1,arr[r-1]);
        }
        if(nxt <= arr[r]) psh(nxt-c+d,r,nxt);
        else if(r+1 < n){
             psh(d+1,r+1,0);  
        }

        // vertical 
        if(r > 0) psh(d+1,r-1,min(c,arr[r-1])); 
        if(r+1 < n) psh(d+1,r+1,min(c,arr[r+1])); 
    }

    cout << dist.get(er,toInd[ec]) << "\n";
}

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