Submission #1108848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108848		8pete8	Text editor (CEOI24_editor)	C++17	100 / 100	252 ms	63228 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6+5,inf=1e18,minf=-1e18,lg=20;
int cost0[mxn+10],costlen[mxn+10],n,len[mxn+10],col[mxn+10];
pii st,ed;
struct seg{
    int v[2*mxn+10];
    void init(){for(int i=0;i<=2*n;i++)v[i]=inf;}
    void update(int pos,int val){
        pos+=n;
        v[pos]=min(v[pos],val);
        for(int i=pos;i>0;i>>=1)v[i>>1]=min(v[i],v[i^1]);
    }
    int qry(int l,int r){
        int ans=inf;
        for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
            if(l&1)ans=min(ans,v[l++]);
            if(!(r&1))ans=min(ans,v[r--]);
        }
        return ans;
    }
}before,after;
int ans=inf;
void computecost0(){
    int cur=st.s;
    after.init(),before.init();
    col[st.f]=st.s;
    for(int i=st.f-1;i>=1;i--)col[i]=min(col[i+1],len[i]+1);
    cur=st.s;
    for(int i=st.f+1;i<=n;i++)col[i]=min(col[i-1],len[i]+1);
    ans=min(ans,abs(st.f-ed.f)+abs(col[ed.f]-ed.s));
    for(int i=1;i<=n;i++){
        cost0[i]=min(col[i]-1+abs(st.f-i),cost0[i]);
        if(i>1)cost0[i]=min(cost0[i],len[i-1]+2-col[i-1]+abs(st.f-i+1));
    }
    for(int i=1;i<=n;i++)before.update(i,-i+cost0[i]),after.update(i,i+cost0[i]);
    for(int i=1;i<=n;i++){
        cost0[i]=min({cost0[i],i+before.qry(1,i-1),after.qry(i+1,n)-i});
    }
}
void computecostlen(){
    for(int i=1;i<=n;i++){
        costlen[i]=len[i]+1-col[i]+abs(i-st.f);
        if(i+1<=n)costlen[i]=min(costlen[i],cost0[i+1]+1);
    }
}
int32_t main(){
    fastio
    cin>>n;
    cin>>st.f>>st.s;
    cin>>ed.f>>ed.s;
    for(int i=1;i<=n;i++){
        cin>>len[i],cost0[i]=costlen[i]=inf;
    }
    computecost0();
    computecostlen();
    col[ed.f]=len[ed.f]+1;
    for(int i=ed.f+1;i<=n;i++)col[i]=min(col[i-1],len[i]+1);
    for(int i=ed.f-1;i>=1;i--)col[i]=min(col[i+1],len[i]+1);
    ans=min(ans,cost0[ed.f]+abs(ed.s-1));
    for(int i=1;i<=n;i++)ans=min(ans,abs(ed.f-i)+costlen[i]+abs(col[i]-ed.s));
    cout<<ans;
}
/*
maybe we can compute min cost of moving for start to line i and the cursor is at len i
how to compute?
ways to get cursor at leni at i
option1 (min of len(start,i)==leni and startpos>=leni) then we can just move
option2 {
    get to pos0 first then use cost 1 to get to len i
    now we need to compute how to get pos0
    just move normally and the cost of getting pos0 at linei is min(poscur,len-poscur) something like this
}
is this all?? YES (i think)


then compute the min cost of moving cursor at line i len i to end
*/

Compilation message (stderr)

Main.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:40:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 |     void init(){for(int i=0;i<=2*n;i++)v[i]=inf;}
      |               ^
Main.cpp:41:32: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   41 |     void update(int pos,int val){
      |                                ^
Main.cpp:46:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     int qry(int l,int r){
      |                        ^
Main.cpp:56:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   56 | void computecost0(){
      |                   ^
Main.cpp: In function 'void computecost0()':
Main.cpp:57:9: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   57 |     int cur=st.s;
      |         ^~~
Main.cpp: At global scope:
Main.cpp:73:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | void computecostlen(){
      |                     ^
Main.cpp:79:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   79 | int32_t main(){
      |              ^

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