Блог пользователя Ynoi

Автор Ynoi, история, 5 лет назад, По-английски
#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,inf=2e9;
struct sgt{
    PII d[N<<2];
    inline PII merge(const PII&A,const PII&B){
        if(A.first<B.first)return make_pair(A.first,min(B.first,min(A.second,B.second)));
        return make_pair(B.first,min(A.first,min(B.second,A.second)));
    }
    void build(int l,int r,int o){
        d[o]=make_pair(inf,inf);
        if(l<r){
            const int mid=l+r>>1;
            build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        }
    }
    void modify(int l,int r,int o,const int&pos,const int&val){
        if(l==r)d[o]=make_pair(val,inf);else{
            const int mid=l+r>>1;
            if(pos<=mid)modify(l,mid,o<<1,pos,val);else modify(mid+1,r,o<<1|1,pos,val);
            d[o]=merge(d[o<<1],d[o<<1|1]);
        }
    }
    PII query(int l,int r,int o,const int&L,const int&R){
        if(L<=l&&r<=R)return d[o];
        const int mid=l+r>>1;
        if(L<=mid&&mid<R)return merge(query(l,mid,o<<1,L,R),query(mid+1,r,o<<1|1,L,R));
        if(L<=mid)return query(l,mid,o<<1,L,R);
        return query(mid+1,r,o<<1|1,L,R);
    }
}R[10];
int a[N],n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<10;++i)R[i].build(1,n,1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        int x=a[i];
        for(int k=0;k<10;++k,x/=10)
            if(x%10)R[k].modify(1,n,1,i,a[i]);
    }
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            a[l]=r;
            for(int k=0;k<10;++k,r/=10)
                if(r%10)R[k].modify(1,n,1,l,a[l]);
                else
                    R[k].modify(1,n,1,l,inf);
        }else{
            unsigned ans=inf;
            for(int i=0;i<10;++i){
                PII f=R[i].query(1,n,1,l,r);
                ans=min(ans,(unsigned)f.first+f.second);
            }
            cout<<(ans==inf?-1LL:ans)<<'\n';
        }
    }
    return 0;
}
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

C++ 14 has better things.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    But in many Chinese contest(such as CSP,NOI),we can't use C++14.So I must know the reason of this compilation error

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think, this verdict also depends on the version of compiler. I have submitted it in another OJ with c++11 and also run it in my local machine with c++11, it compiles fine in both cases.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    This code is mine. Thanks for your help. But I wonder why the code can run correctly with C++14.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      In codeforces the compiler versions used for c++11 and c++14 are different. I think, this bug was fixed in later versions.