Ynoi's blog

By Ynoi, history, 15 months ago, In English

Today I have received my T-shirt of Global Round 13

(only change the number of the round)

Btw,how does other round's T-shirts look like?I have only seen GR2,9,10,13 from me or my classmates.

(Probably all the T-shirt for writers is same,I guess.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

By Ynoi, history, 3 years ago, In English
#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;
}

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it