Submission #174692

#	Time	Username	Problem	Language	Result	Execution time	Memory
174692		awlintqaa	Garaža (COCI17_garaza)	C++14	160 / 160	3392 ms	46732 KiB

garaza

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
ll n,q;
ll a[100009];
struct NODE{
        ll ans;
        vpll p,s;
        NODE(){ans=0;}
}tree[400009];
ll calc(vpll x,vpll y){
        ll crnt=0,j=0,ans=0;
        for(auto u:x){
                while(__gcd(u.fi,y[j].fi)!=1 && j<y.size())crnt+=y[j++].se;
                ans+=u.se*crnt;
        }
        return ans;
}
vpll createp(vpll x,vpll y){
        vpll ret;
        for(auto u:x)ret.pb(u);
        ll G=ret[ret.size()-1].fi;
        for(auto u:y){
                G=__gcd(G,u.fi);
                if(G==ret[ret.size()-1].fi)ret[ret.size()-1].se+=u.se;
                else ret.pb({G,u.se});
        }
        return ret;
}
vpll creates(vpll x,vpll y){
        reverse(x.begin(),x.end());
        reverse(y.begin(),y.end());
        vpll ret=createp(y,x);
        reverse(ret.begin(),ret.end());
        return ret;
}
NODE merge(NODE x,NODE y){
        NODE ret;
        ret.ans=x.ans+y.ans+calc(x.s,y.p);
        ret.p=createp(x.p,y.p);
        ret.s=creates(x.s,y.s);
        return ret;
}
void build(int node,int l,int r){
        if(l==r){
                tree[node].ans=(a[l]!=1);
                tree[node].p.pb({a[l],1});
                tree[node].s.pb({a[l],1});
                return ;
        }
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        tree[node]=merge(tree[node*2],tree[node*2+1]);
}
NODE query(int node,int l,int r,int s,int e){
        if(s<=l && e>=r)return tree[node];
        if(s<=mid && e>=mid+1)return merge(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
        else if(s<=mid)return query(node*2,l,mid,s,e);
        else return query(node*2+1,mid+1,r,s,e);
}
void upd(int node,int l,int r,int k,ll x){
        if(l==r){
                tree[node].ans=(x!=1);
                tree[node].p.clear(),tree[node].p.pb({x,1});
                tree[node].s.clear(),tree[node].s.pb({x,1});
                return ;
        }
        if(k<=mid)upd(node*2,l,mid,k,x);
        else upd(node*2+1,mid+1,r,k,x);
        tree[node]=merge(tree[node*2],tree[node*2+1]);
}
int main(){
        cin>>n>>q;
        for(int i=0;i<n;i++)cin>>a[i];
        build(1,0,n-1);
        while(q--){
                int t;cin>>t;
                if(t==1){
                        int k,val;
                        cin>>k>>val,k--,val;
                        upd(1,0,n-1,k,val);
                }
                if(t==2){
                        int l,r;
                        cin>>l>>r,l--,r--;
                        cout<<query(1,0,n-1,l,r).ans<<endl;
                }
        }
}

Compilation message (stderr)

garaza.cpp: In function 'll calc(vpll, vpll)':
garaza.cpp:38:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(__gcd(u.fi,y[j].fi)!=1 && j<y.size())crnt+=y[j++].se;
                                                 ~^~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:104:44: warning: right operand of comma operator has no effect [-Wunused-value]
                         cin>>k>>val,k--,val;
                                            ^

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