Submission #1236547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236547		hainam2k9	Garaža (COCI17_garaza)	C++20	160 / 160	275 ms	8264 KiB

garaza

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n,q,a[MAXN],r[MAXN];
int STgcd[MAXN<<2];
void buildSTgcd(int id, int l, int r){
    if(l==r) return STgcd[id]=a[l], void();
    int mid=(l+r)>>1;
    buildSTgcd(id<<1,l,mid);
    buildSTgcd(id<<1|1,mid+1,r);
    STgcd[id]=__gcd(STgcd[id<<1],STgcd[id<<1|1]);
}
void updateGCD(int id, int l, int r, int pos, int val){
    if(pos<l||r<pos) return;
    if(l==r) return STgcd[id]=val, void();
    int mid=(l+r)>>1;
    updateGCD(id<<1,l,mid,pos,val);
    updateGCD(id<<1|1,mid+1,r,pos,val);
    STgcd[id]=__gcd(STgcd[id<<1],STgcd[id<<1|1]);
}
int walkRight(int id, int l, int r, int pos){ //how to walk
    static int curgcd=0;
    if(id==1) curgcd=0;
    if(r<pos) return -1;
    if(l==r){
        curgcd=__gcd(curgcd,a[l]);
        if(curgcd==1) return l-1;
        return -1;
    }
    int mid=(l+r)>>1, rs=walkRight(id<<1,l,mid,pos);
    if(rs==-1){
        if(mid+1>=pos&&__gcd(curgcd,STgcd[id<<1|1])>1) curgcd=__gcd(curgcd,STgcd[id<<1|1]);
        else rs=walkRight(id<<1|1,mid+1,r,pos);
    }
    return rs;
}
int walkLeft(int id, int l, int r, int pos, const int& val){
    static int curgcd=0;
    if(id==1) curgcd=0;
    if(l>pos) return -1;
    if(l==r){
        curgcd=__gcd(curgcd,a[l]);
        if(curgcd<val) return l+1;
        return -1;
    }
    int mid=(l+r)>>1, rs=walkLeft(id<<1|1,mid+1,r,pos,val);
    if(rs==-1){
        if(mid<=pos&&__gcd(curgcd,STgcd[id<<1])>=val) curgcd=__gcd(curgcd,STgcd[id<<1]);
        else rs=walkLeft(id<<1,l,mid,pos,val);
    }
    return rs;
}

pair<ll,int> STsum[MAXN<<2];
int lazy[MAXN<<2];
inline void down(int id, int l, int r){
    if(lazy[id]==-1) return;
    lazy[id<<1]=lazy[id<<1|1]=lazy[id];
    STsum[id<<1].se=STsum[id<<1|1].se=lazy[id];
    int mid=(l+r)>>1;
    STsum[id<<1].fi=1ll*(mid-l+1)*lazy[id], STsum[id<<1|1].fi=1ll*(r-mid)*lazy[id];
    lazy[id]=-1;
}
void buildSTsum(int id, int l, int r){
    if(l==r){
        STsum[id].fi=STsum[id].se=walkRight(1,0,n+1,l);
        return;
    }
    int mid=(l+r)>>1;
    buildSTsum(id<<1,l,mid);
    buildSTsum(id<<1|1,mid+1,r);
    STsum[id].fi=STsum[id<<1].fi+STsum[id<<1|1].fi;
    STsum[id].se=STsum[id<<1|1].se;
}
void update(int id, int l, int r, int u, int v, int val){
    if(v<l||r<u||u>v) return;
    if(u<=l&&r<=v){
        lazy[id]=STsum[id].se=val;
        STsum[id].fi=1ll*(r-l+1)*val;
        return;
    }
    down(id,l,r);
    int mid=(l+r)>>1;
    update(id<<1,l,mid,u,v,val);
    update(id<<1|1,mid+1,r,u,v,val);
    STsum[id].fi=STsum[id<<1].fi+STsum[id<<1|1].fi;
    STsum[id].se=STsum[id<<1|1].se;
}
int walk(int id, int l, int r, const int& val){
    if(l==r){
        if(STsum[id].se>=val) return l-1;
        return l;
    }
    down(id,l,r);
    int mid=(l+r)>>1;
    if(STsum[id<<1].se>=val) return walk(id<<1,l,mid,val);
    return walk(id<<1|1,mid+1,r,val);
}
ll getsum(int id, int l, int r, int u, int v){
    if(v<l||r<u||u>v) return 0;
    if(u<=l&&r<=v) return STsum[id].fi;
    down(id,l,r);
    int mid=(l+r)>>1;
    return getsum(id<<1,l,mid,u,v)+getsum(id<<1|1,mid+1,r,u,v);
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    memset(lazy,-1,sizeof(lazy));
    cin >> n >> q;
    for(int i = 1; i<=n; ++i)
        cin >> a[i];
    a[0]=a[n+1]=1;
    buildSTgcd(1,0,n+1);
    buildSTsum(1,1,n);
    while(q--){
        int type,l,r;
        cin >> type >> l >> r;
        if(type==1){
            a[l]=r, updateGCD(1,0,n+1,l,r);
            int pos=walkLeft(1,0,n+1,l,r), nxt=l, GCD=r;
            while(pos>0){
                update(1,1,n,pos,nxt,walkRight(1,0,n+1,pos));
                nxt=pos-1, GCD=__gcd(GCD,a[pos-1]), pos=walkLeft(1,0,n+1,l,GCD);
            }
            pos=walk(1,1,n,l)+1;
            update(1,1,n,pos,nxt,l-1);
        }else{
            int pos=max(l-1,walk(1,1,n,r));
            cout << getsum(1,1,n,l,pos)+max(0ll,1ll*(r-pos)*r)-1ll*r*(r-1)/2+1ll*(l-1)*(l-2)/2 << "\n";
        }
    }
}

Compilation message (stderr)

garaza.cpp: In function 'int main()':
garaza.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:127:45: note: in expansion of macro 'fo'
  127 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
garaza.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:127:45: note: in expansion of macro 'fo'
  127 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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