제출 #1343246

#제출 시각아이디문제언어결과실행 시간메모리
1343246jmuzhenBikeparking (EGOI24_bikeparking)C++20
0 / 100
1096 ms51952 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define DEBUG 0
#define printf if(DEBUG) printf

constexpr int MAXN = 3e5+10;

// Usage (range sum): using ST=LazySeg<InfoSum<long long>,AddSetTag<long long>>; ST st(n,0LL); st.range_apply(l,r,ST::TagT::add(v)); auto s=st.query(l,r).sum;
// Info: data schema, apply and merge ops. Tag: a lazy update "payload".

template <class T> struct lazy_numeric_ops {
    static T zero(){ return T(); }
    static T add(const T& a,const T& b){ return a+b; }
    static T scale(const T& v,int len){ return v*T(len); }
    static bool isZero(const T& v){ return v==zero(); }
    static bool less(const T& a,const T& b){ return a<b; }
    static T minId(){ return numeric_limits<T>::max(); }
    static T maxId(){ return numeric_limits<T>::lowest(); }
};
template <class T,class Ops = lazy_numeric_ops<T>>
struct AddSetTag {
    T addv,setv; bool hset;
    AddSetTag(T a=Ops::zero(),T s=Ops::zero(),bool h=false): addv(a),setv(s),hset(h) {}
    static AddSetTag add(const T& v){ return AddSetTag(v); }
    static AddSetTag set(const T& v){ return AddSetTag(Ops::zero(),v,true); }
    bool isId() const { return !hset && Ops::isZero(addv); }
    T setVal() const { return Ops::add(setv,addv); } // value after applying a set-tag
    void applyTo(T& x) const { x = hset ? setVal() : Ops::add(x,addv); } // elementwise
    void compose(const AddSetTag& t){ // apply t after current
        if (t.hset){ hset=true; setv=t.setv; addv=t.addv; }
        else addv = Ops::add(addv,t.addv);
    }
};
template <class T,class Ops = lazy_numeric_ops<T>, class Tag = AddSetTag<T,Ops>>
struct InfoSum {
    using V = T; T sum;
    InfoSum(T s=Ops::zero()): sum(s) {}
    static InfoSum from(const T& x){ return InfoSum(x); }
    static InfoSum merge(const InfoSum& a,const InfoSum& b){ return InfoSum(Ops::add(a.sum,b.sum)); }
    void apply(const Tag& t,int len){
        if (t.hset) sum = Ops::scale(t.setVal(),len);
        else sum = Ops::add(sum,Ops::scale(t.addv,len));
    }
};
template <class T,class Ops = lazy_numeric_ops<T>, class Tag = AddSetTag<T,Ops>>
struct InfoMin {
    using V = T; T mn;
    InfoMin(T v=Ops::minId()): mn(v) {}
    static InfoMin from(const T& x){ return InfoMin(x); }
    static InfoMin merge(const InfoMin& a,const InfoMin& b){ return InfoMin(Ops::less(a.mn,b.mn)?a.mn:b.mn); }
    void apply(const Tag& t,int){ mn = t.hset ? t.setVal() : Ops::add(mn,t.addv); }
};
template <class T,class Ops = lazy_numeric_ops<T>, class Tag = AddSetTag<T,Ops>>
struct InfoMax {
    using V = T; T mx;
    InfoMax(T v=Ops::maxId()): mx(v) {}
    static InfoMax from(const T& x){ return InfoMax(x); }
    static InfoMax merge(const InfoMax& a,const InfoMax& b){ return InfoMax(Ops::less(a.mx,b.mx)?b.mx:a.mx); }
    void apply(const Tag& t,int){ mx = t.hset ? t.setVal() : Ops::add(mx,t.addv); }
};
template <class T,class Ops = lazy_numeric_ops<T>, class Tag = AddSetTag<T,Ops>>
struct InfoSumMinMax {
    using V = T; T sum,mn,mx;
    InfoSumMinMax(T s=Ops::zero(),T mi=Ops::minId(),T ma=Ops::maxId()): sum(s),mn(mi),mx(ma) {}
    static InfoSumMinMax from(const T& x){ return InfoSumMinMax(x,x,x); }
    static InfoSumMinMax merge(const InfoSumMinMax& a,const InfoSumMinMax& b){
        T mi = Ops::less(a.mn,b.mn)?a.mn:b.mn, ma = Ops::less(a.mx,b.mx)?b.mx:a.mx;
        return InfoSumMinMax(Ops::add(a.sum,b.sum),mi,ma);
    }
    void apply(const Tag& t,int len){
        if (t.hset){ T v=t.setVal(); sum=Ops::scale(v,len); mn=mx=v; }
        else { sum=Ops::add(sum,Ops::scale(t.addv,len)); mn=Ops::add(mn,t.addv); mx=Ops::add(mx,t.addv); }
    }
};

template <class Info, class Tag>
struct LazySeg {
    using V = typename Info::V;
    using TagT = Tag;
    int s,e; Info info; Tag lz; LazySeg *l,*r; V uni;
    LazySeg(int n,const V& initv=V()): LazySeg(0,n-1,initv) {}
    LazySeg(int ss,int ee,const V& initv): s(ss),e(ee),info(),lz(),l(nullptr),r(nullptr),uni(initv){ info.apply(Tag::set(uni),e-s+1); }
    LazySeg(int ss,int ee,const vector<V>& a): LazySeg(ss,ee,a,ss) {}
    LazySeg(int ss,int ee,const vector<V>& a,int off): s(ss),e(ee),info(),lz(),l(nullptr),r(nullptr),uni(V()){
        if (s==e) uni=a[s-off], info = Info::from(uni);
        else { int m=(s+e)>>1; l=new LazySeg(ss,m,a,off); r=new LazySeg(m+1,ee,a,off); pull(); }
    }
    void apply(const Tag& t){ info.apply(t,e-s+1); if (!l) t.applyTo(uni); else lz.compose(t); }
    void make_child(){ if (s==e || l) return; int m=(s+e)>>1; l=new LazySeg(s,m,uni); r=new LazySeg(m+1,e,uni); }
    void push(){ if (lz.isId() || s==e) return; make_child(); l->apply(lz); r->apply(lz); lz=Tag(); }
    void pull(){ info = Info::merge(l->info,r->info); }
    void range_apply(int L,int R,const Tag& t){
        if (R<s || e<L) return;
        if (L<=s && e<=R){ apply(t); return; }
        if (!l) make_child(); push(); l->range_apply(L,R,t); r->range_apply(L,R,t); pull();
    }
    Info query(int L,int R){
        if (R<s || e<L) return Info();
        if (L<=s && e<=R) return info;
        if (!l){ int ls=max(s,L), rs=min(e,R), ov=rs-ls+1; if (ov<=0) return Info(); Info res; res.apply(Tag::set(uni),ov); return res; }
        push(); return Info::merge(l->query(L,R),r->query(L,R));
    }
    int first_le(int L,int R,const V& v){ // first i in [L,R] with a[i]<=v, else -1
        // To get first >= (or >), use mx instead and change mn>v test to mx<v (or <=v).
        return first_le(L,R,v,[](const V& a,const V& b){ return a<b; });
    }
    template <class Less> int first_le(int L,int R,const V& v,Less less){
        if (R<s || e<L || less(v,info.mn)) return -1; if (s==e || !l) return max(s,L); 
        push(); int res=l->first_le(L,R,v,less); return res!=-1 ? res : r->first_le(L,R,v,less);
    }
    ~LazySeg(){ delete l; delete r; }
};


signed main() {
    int n;cin>>n;
    vector<int> x(n),y(n);
    for(int i = 0; i < n; i++) cin>>x[i];
    // populate segtree with available slots first
    LazySeg<InfoSum<int>, AddSetTag<int>> seg(0, n-1, x);

    for(int i = 0; i < n; i++) cin>>y[i];

    int score = 0;

    // for(int i = 0; i < n; i++) {
    for(int i = n-1; i >= 0; i--) {
        printf("i=%d\n",i);
        // demand y[i]
        int demand = y[i];
        // binary search
        // starting from some j, down to 0, what is the earliest one that still sums within some value
        auto find_earliest_idx_sum_le = [&](int j, int target) {
            int l = 0, r = j; // length, calculated as j - x
            int best = -1;
            while (l <= r) {
                int mid = l+(r-l)/2;
                int x = j - mid;
                int sum = seg.query(x, j).sum;
                if (sum <= target) {
                    // can keep going left so lebgth increase
                    best = x;
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
            return best;
        };

        int j = find_earliest_idx_sum_le(i-1, demand);
        printf("find j=%d\n",j);
        if (j == -1) {
            
        }
        else {
            int sum = seg.query(j, i-1).sum;
             printf("take sum=%d\n",sum);

            demand -= sum;
            score += sum; // +1 each
            printf("score += %d\n",sum);

            seg.range_apply(j, i-1, AddSetTag<int>::set(0));

            // check last partial
            if (demand > 0 && j-1 >= 0) {
                int self = seg.query(j-1,j-1).sum;
                int take = min(self, demand);
             printf("take partial=%d from %d\n",take, j-1);

                seg.range_apply(j-1, j-1, AddSetTag<int>::add(-take));
                demand -= take;
                score += take;
                printf("score += %d\n",take);

            }
        }

        if (demand > 0) {
            // check i itself
            int self = seg.query(i,i).sum;
            int take = min(self, demand);
             printf("take self=%d\n",take);

            seg.range_apply(i, i, AddSetTag<int>::add(-take));
            demand -= take;
            if (demand > 0) {
                score -= demand;
                printf("score -= %d\n",demand);
            }
        }
    }

    cout<<score<<endl;

}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:131:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  131 |         printf("i=%d\n",i);
      |                   ~^    ~
      |                    |    |
      |                    int  long long int
      |                   %lld
Main.cpp:155:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  155 |         printf("find j=%d\n",j);
      |                        ~^    ~
      |                         |    |
      |                         int  long long int
      |                        %lld
Main.cpp:161:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  161 |              printf("take sum=%d\n",sum);
      |                               ~^    ~~~
      |                                |    |
      |                                int  long long int
      |                               %lld
Main.cpp:165:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  165 |             printf("score += %d\n",sum);
      |                              ~^    ~~~
      |                               |    |
      |                               int  long long int
      |                              %lld
Main.cpp:173:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  173 |              printf("take partial=%d from %d\n",take, j-1);
      |                                   ~^            ~~~~
      |                                    |            |
      |                                    int          long long int
      |                                   %lld
Main.cpp:173:44: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  173 |              printf("take partial=%d from %d\n",take, j-1);
      |                                           ~^          ~~~
      |                                            |           |
      |                                            int         long long int
      |                                           %lld
Main.cpp:178:35: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  178 |                 printf("score += %d\n",take);
      |                                  ~^    ~~~~
      |                                   |    |
      |                                   int  long long int
      |                                  %lld
Main.cpp:187:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  187 |              printf("take self=%d\n",take);
      |                                ~^    ~~~~
      |                                 |    |
      |                                 int  long long int
      |                                %lld
Main.cpp:193:35: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  193 |                 printf("score -= %d\n",demand);
      |                                  ~^    ~~~~~~
      |                                   |    |
      |                                   int  long long int
      |                                  %lld
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...