Submission #1361153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361153		Aviansh	Tycho (BOI23_tycho)	C++20	13 / 100	8 ms	436 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = LLONG_MAX;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int b,p,d,n;
    cin >> b >> p >> d >> n;
    int las = 0;
    map<int,int>mp;
    mp[0]=0;
    int delta = 0;
    int laz = 0;
    int sum = 0;
    auto join = [&] (int a){
        ///merge las-a range into dp
        int len = a-las-1;
        int base = (len/p)*d;
        int tillpos = p-len%p;
        ///add base to starting point delta.
        if(base){
            laz+=base;
        }
        ///now make range tillpos-p in this shifted version
        ///(tillpos+delta)%p -> delta
        tillpos-=delta;
        tillpos%=p;
        tillpos+=p;
        tillpos%=p;
        int tillneg = p-delta;
        tillneg%=p;
        tillneg+=p;
        tillneg%=p;
        if(tillneg==tillpos){
            //laz+=d;
        }
        else if(tillpos==0){
            //prefix
            laz+=d;
            if(tillneg){
                mp[tillneg]-=d;
                sum-=d;
            }
            else{
                laz-=d;
            }
        }
        else if(tillneg==0){
            //suffix
            auto it1 = mp.lower_bound(tillpos);
            if(it1==mp.end()){
                //do nothing
            }
            else{
                int fir = (*it1).first;
                int ol = (*it1).second;
                sum-=ol;
                ol+=d;
                mp.erase(it1);
                if(ol<0){
                    mp[fir]=ol;
                    sum+=ol;
                }
            }
        }
        else if(tillneg>tillpos){
            ///one single range
            auto it1 = mp.lower_bound(tillpos);
            auto it2 = mp.lower_bound(tillneg);
            if(it1==it2){
                //nothing happens
            }
            else{
                int add = d;
                if(tillneg){
                    mp[tillneg]-=d;
                    sum-=d;
                }
                else{
                    laz-=d;
                }
                contb:
                    it1 = mp.lower_bound(tillpos);
                    if(it1!=mp.end()){
                        int fir = (*it1).first;
                        int ol = (*it1).second;
                        sum-=ol;
                        ol+=add;
                        mp.erase(it1);
                        if(ol<0){
                            mp[fir]=ol;
                            sum+=ol;
                        }
                        else if(ol>0){
                            add=ol;
                            goto contb;
                        }
                    }
            }
        }
        else if(tillneg<tillpos){
            ///prefix and suffix
            ///MAY CAUSE BAD
            laz+=d;
            if(tillneg){
                mp[tillneg]-=d;
                sum-=d;
            }
            else{
                laz-=d;
            }
            auto it1 = mp.lower_bound(tillpos);
            if(it1==mp.end()){
                //do nothing
            }
            else{
                int add = d;
                conta:
                    it1 = mp.lower_bound(tillpos);
                    if(it1!=mp.end()){
                        int fir = (*it1).first;
                        int ol = (*it1).second;
                        sum-=ol;
                        ol+=add;
                        mp.erase(it1);
                        if(ol<0){
                            mp[fir]=ol;
                            sum+=ol;
                        }
                        else if(ol>0){
                            add=ol;
                            goto conta;
                        }
                    }
            }
            if(p+sum<-1){
                ///end is lower than start.
                ///must reset
                ///assume mp[0]=0;
                int rval = p+sum;
                laz+=rval;
                rval=-rval;
                while(mp.size()&&rval){
                    auto it = mp.begin();
                    if(-(*it).second<=rval){
                        rval+=(*it).second;
                        sum-=(*it).second;
                        mp.erase(it);

                    }
                    else{
                        sum+=rval;
                        mp[(*it).first]+=rval;
                        rval=0;
                    }
                }
                mp[0]=0;
            }
        }
        else{
            //do nothing
        }

        //shift
        delta += (len+1)%p;
        delta%=p;
        las=a;
    };
    while(n--){
        int a;
        cin >> a;
        join(a);
    }
    join(b);
    int curr = laz;
    int ans = inf;
    las = 0;
    assert(mp[0]==0);
    for(pair<int,int>a:mp){
        curr+=a.second;
        curr+=(a.first-las);
        las=a.first;
        ans=min(ans,curr);
    }
    ans+=b;
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 5 / 5
• Subtask 4: 0 / 7
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 35
• Subtask 8: 0 / 10