제출 #332513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332513		Reim	Garaža (COCI17_garaza)	C++14	0 / 160	154 ms	11860 KiB

garaza

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define R(x) ((x<<1)+1)
#define L(x) (x<<1)
#define INF 1e9+1
using namespace std;
typedef long long int ll;

struct num{
    int qtdp, qtds, prefix, sufix, first, last;
    ll ans;
};

int gdc(int A,int B){
    if(B==0)
        return A;
    else
        return gdc(B,A%B);
}

int V[100005], Q, N;
num seg3[4*100005];

num join(num A,num B){
    num resp;
    int Y;
    resp.ans=A.ans+B.ans;
    resp.first=A.first;
    if(B.last!=0)
        resp.last=B.last;
    else
        resp.last=A.first;
    if(A.sufix==0 && B.sufix==0){
        Y=gdc(A.prefix,B.prefix);
        if(Y>1){
            resp.prefix=Y;
            resp.qtdp=A.qtdp+B.qtdp;
            resp.ans+=(A.qtdp*B.qtdp);
            resp.sufix=0;
            resp.qtds=0;
        }
        else{
            resp.prefix=A.prefix;
            resp.qtdp=A.qtdp;
            resp.sufix=B.prefix;
            resp.qtds=B.qtdp;
        }
    }
    else if(A.sufix==0 && B.sufix!=0){
        Y=gdc(A.prefix,B.prefix);
        if(Y>1){
            resp.prefix=Y;
            resp.qtdp=A.qtdp+B.qtdp;
            resp.ans+=(A.qtdp*B.qtdp);
            resp.sufix=B.sufix;
            resp.qtds=B.qtds;
        }
        else{
            resp.prefix=A.prefix;
             resp.qtdp=A.qtdp;
            resp.sufix=B.sufix;
            resp.qtds=B.qtds;
        }
    }
    else if(A.sufix!=0 && B.sufix==0){
        Y=gdc(A.sufix,B.prefix);
        if(Y>1){
            resp.prefix=A.prefix;
            resp.qtdp=A.qtdp;
            resp.ans+=(A.qtds*B.qtdp);
            resp.sufix=Y;
            resp.qtds=A.qtds+B.qtdp;
        }
        else{
            resp.prefix=A.prefix;
            resp.qtdp=A.qtdp;
            resp.sufix=B.prefix;
            resp.qtds=B.qtdp;
        }
    }
    else if(A.sufix!=0 && B.sufix!=0){
        Y=gdc(A.sufix,B.prefix);
        if(Y>1){
            resp.ans+=(A.qtds*B.qtdp);
        }
        resp.prefix=A.prefix;
        resp.qtdp=A.qtdp;
        resp.sufix=B.sufix;
        resp.qtds=B.qtds;
    }

    return resp;
}

void build(int node,int l,int r){
    if(l==r){
        seg3[node].qtdp=1;
        seg3[node].prefix=V[l];
        seg3[node].sufix=seg3[node].qtds=0;
        if(V[l]>1)
            seg3[node].ans=1;
        else
            seg3[node].ans=0;
        return ;
    }
    int meio;
    meio=((l+r)>>1);
    build(L(node),l,meio);
    build(R(node),meio+1,r);

    seg3[node]=join(seg3[L(node)],seg3[R(node)]);
}

void update(int node,int l,int r,int i,int val){
    if(i==l && r==l){
        V[l]=val;
        seg3[node].qtdp=1;
        seg3[node].last=seg3[node].first=seg3[node].prefix=V[l];
        seg3[node].sufix=seg3[node].qtds=0;
        if(V[l]>1)
            seg3[node].ans=1;
        else
            seg3[node].ans=0;
        return ;
    }
    int meio;
    meio=((l+r)>>1);
    if(l<=i && i<=meio) update(L(node),l,meio,i,val);
    if(meio+1<=i && i<=r) update(R(node),meio+1,r,i,val);

    seg3[node]=join(seg3[L(node)],seg3[R(node)]);
}

num query(int node,int l,int r,int i,int j){
    if(r<i || j<l) return {0,0,0,0,0};
    if(i<=l && r<=j) return seg3[node];
    int meio;
    meio=((l+r)>>1);
    num resp1, resp2;
    resp1=query(L(node),l,meio,i,j);
    resp2=query(R(node),meio+1,r,i,j);
    return join(resp1,resp2);
}

int main(){_
    cin>>N>>Q;
    for(int i=1;i<=N;i++){
        cin>>V[i];
    }
    build(1,1,N);

    while(Q--){
        int A, B, C;
        cin>>A>>B>>C;
        if(A==1)
            update(1,1,N,B,C);
        else
            cout<<query(1,1,N,B,C).ans<<'\n';
    }

    return 0;
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40