Submission #1176987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176987		LmaoLmao	Board (CEOI13_board)	C++20	80 / 100	165 ms	5976 KiB

board

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e5;
const int INF = 1e9;

int S[N*4+5],lz[N*4+5];

void push(int id,ll l,ll r) {
    if(lz[id]!=-1) {
        ll m=(l+r)/2;
        S[id*2]=lz[id]*(m-l+1);
        S[id*2+1]=lz[id]*(r-m);
        lz[id*2]=lz[id];
        lz[id*2+1]=lz[id];
        lz[id]=-1;
    }
}

void update(int id,ll l,ll r,int u,int v,ll x) {
    if(v < l || r < u) return;
    if(u <=l && r <= v) {
        lz[id]=x;
        S[id]=x*(r-l+1);
        return;
    }
    push(id,l,r);
    int m=(l+r)/2;
    update(id*2,l,m,u,v,x);
    update(id*2+1,m+1,r,u,v,x);
    S[id]=S[id*2]+S[id*2+1];
}
int get(int id,int l,int r,int u,int v) {
    if(v < l || r < u) return 0;
    if(u <=l && r <=v) {
        return S[id];
    }
    push(id,l,r);
    int m=(l+r)/2;
    ll t=get(id*2,l,m,u,v);
    ll t1=get(id*2+1,m+1,r,u,v);
    return t+t1;
}
vector<int> solve(string s) {
    vector<int> res;
    int n=s.size();
    int sz=1;
    for(int i=1;i<=4*N;i++) lz[i]=-1;
    update(1,1,N,1,N,0);
    update(1,1,N,1,1,1);
    for(int i=0;i<n;i++) {
        if(s[i]=='1') {
            sz++;
        }
        if(s[i]=='2') {
            sz++;
            update(1,1,N,sz,sz,1);
        }
        if(s[i]=='U') {
            update(1,1,N,sz,sz,0);
            sz--;
        }
        if(s[i]=='L') {
            int l=1,r=sz;
            int t=0;
            int cur=get(1,1,N,1,sz);
            while(l<=r) {
                int mid=(l+r)/2;
                if(get(1,1,N,1,mid)==cur) {
                    r=mid-1;
                    t=mid;
                }
                else l=mid+1;
            }

            update(1,1,N,t,t,0);
            if(t<sz)update(1,1,N,t+1,sz,1);

        }
        if(s[i]=='R') {
            int l=1,r=sz-1;
            int t=0;
            int cur=get(1,1,N,1,sz);
            while(l<=r) {
                int mid=(l+r)/2;
                if(cur-get(1,1,N,1,mid)!=sz-mid) {
                    l=mid+1;
                    t=mid+1;
                }
                else r=mid-1;
            }
            update(1,1,N,t,t,1);
            if(t<sz) update(1,1,N,t+1,sz,0);
        }
    }
    for(int i=1;i<=sz;i++){
        res.push_back(get(1,1,N,i,i));
        //cout << *res.rbegin();
    }
    //cout << endl;
    return res;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a,b;
    cin >> a >> b;
    vector<int> posx,posy;
    posx=solve(a);
    posy=solve(b);
    if(posx.size()>posy.size()) swap(posx,posy);
    int ans=1e9;
    int dif=posy.size()-posx.size();
    for(int i=0;i<posx.size();i++) {
        if(i==posx.size()-1) {
            if(posx[i]==posy[i]) cout << dif; else dif+1;
            return 0;
        }
        if(posx[i]!=posy[i]) {
            dif=posy.size()+posx.size();
            int cur=0;
            while(i<posx.size()) {
                cur=cur*2+posx[i]-posy[i];
                ans=min(ans,dif+abs(cur)-2*i-2);
                if(cur==3) break;
                i++;
            }
            cout << ans;
            return 0;
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10