Submission #720826

#	Time	Username	Problem	Language	Result	Execution time	Memory
720826		cpptowin	Garaža (COCI17_garaza)	C++14	160 / 160	925 ms	42320 KiB

garaza

#include<bits/stdc++.h>
#define db double
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N maxn
#define fi first
#define se second
#define pb push_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000000
#define pii pair<int,int>
#define vii vector<pii>
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(j<<1))
#define vi vector<int>
#define vvi vector<vector<int>>
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int M = 1 << 24;
int m, n, t, k, a[maxn], ans, b[maxn], c[maxn], d[maxn];
int dp[maxn], tong;
vector<int> zero;
struct node
{
    vector<pii> L, R;
    int val;
    node()
    {
        L.clear();
        R.clear();
        val = 0;
    }
};
struct IT
{
    int n;
    vector<node> st;
    IT(int _n): n(_n),st(4*_n+5){};
    node add(node x, node y, int l, int r)
    {
        node res;
        res.val=x.val+y.val;
        int v=x.L.back().fi;
        res.L=x.L;
        for (auto u : y.L)
        {
            v = __gcd(v,u.fi);
            if (v==res.L.back().fi)continue;
            res.L.pb({v,u.se});
        }
        v=y.R.back().fi;
        res.R=y.R;
        for (pii u : x.R)
        {
            v=__gcd(v, u.fi);
            if(v==res.R.back().fi)continue;
            res.R.pb({v,u.se});
        }
        if (__gcd(x.R[0].fi, y.L[0].fi)==1) return res;
        int j=0;
        while (j+1<y.L.size()&& __gcd(x.R[0].fi, y.L[j + 1].fi)>1) ++j;
        for (int i=0;i<x.R.size(); i++)
        {
            while (j>=0&& __gcd(x.R[i].fi, y.L[j].fi)==1) --j;
            if (j<0) break;
            res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
        }
        return res;
    }
    void build(int id, int l, int r)
    {
        if (l==r)
        {
            st[id].L.pb({a[l],l});
            st[id].R.pb({a[l],l});
            st[id].val =(a[l]> 1);
            return;
        }
        int mid=(l+r)>> 1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        st[id]=add(st[id<<1],st[id<<1|1],l,r);
    }
    void update(int id,int l,int r,int pos)
    {
        if (l==r)
        {
            st[id].L[0].fi = a[l];
            st[id].R[0].fi = a[l];
            st[id].val =(a[l]>1);
            return;
        }
        int mid=(l+r)>>1;
        if (pos <= mid) update(id << 1, l, mid, pos);
        else update(id << 1 | 1, mid + 1, r, pos);
        st[id] = add(st[id << 1], st[id << 1 | 1], l, r);
    }
    node get(int id, int l, int r, int u, int v)
    {
        if (u <= l && r <= v) return st[id];
        int mid = (l + r) >> 1;
        if (v <= mid) return get(id << 1, l, mid, u, v);
        if (mid + 1 <= u) return get(id << 1 | 1, mid + 1, r, u, v);
        return add(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v), max(l, u), min(r, v));
    }
};
void process()
{
    cin >> n >> m;
    fo(i,1,n) cin >> a[i];
    IT tree(n);
    tree.build(1,1,n);
    while (m--)
    {
        int l, r;
        cin >> t >> l >> r;
        if (t == 1)
        {
            a[l] = r;
            tree.update(1,1,n,l);
        }
        else cout << tree.get(1,1,n,l, r).val << '\n';
    }
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    process();
}

Compilation message (stderr)

garaza.cpp: In member function 'node IT::add(node, node, long long int, long long int)':
garaza.cpp:82:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while (j+1<y.L.size()&& __gcd(x.R[0].fi, y.L[j + 1].fi)>1) ++j;
      |                ~~~^~~~~~~~~~~
garaza.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i=0;i<x.R.size(); i++)
      |                      ~^~~~~~~~~~~
garaza.cpp:87:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
      |                       ~^~~~~~~~~~~~~~
garaza.cpp:87:78: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             res.val+=(i==x.R.size()-1?x.R[i].se-l+1:x.R[i].se-x.R[i+1].se)*(j==y.L.size()-1?r-y.L[0].se+1:y.L[j+1].se-y.L[0].se);
      |                                                                             ~^~~~~~~~~~~~~~
garaza.cpp: At global scope:
garaza.cpp:146:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  146 | main()
      | ^~~~

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