oj.uz

Submission #81198

# Submission time Handle Problem Language Result Execution time Memory
81198 2018-10-24T04:30:06 Z luckyboy Garaža (COCI17_garaza) C++14
160 / 160
 1286 ms 40360 KB 
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 500005
#define pii pair <int,int>
#define Task "Gara"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
struct Node
{
    long long cnt;
    vector <pii> pre,suf;
}t[maxn << 2];
int n,m,a[maxn];
void Add(vector <pii> &x,vector <pii> y)
{
    if (!x.size() || !y.size()) return;
    int cur = x.back().F;
    int i = 0;
    for (; i < y.size();++i)
        if (__gcd(cur,y[i].F) == cur) x.back().S += y[i].S;
        else break;
    for (;i < y.size();++i)
    {
        long long ww = 0;
        int r = i;
        cur = __gcd(cur,y[i].F);
        while (r < y.size() && cur == __gcd(cur,y[r].F))
        {
            ww += y[r].S;
            ++r;
        }
        x.pb(mp(cur,ww));
        i = r - 1;
    }
}
Node Merge(Node &a,Node &b)
{
    Node res;
    res.cnt = a.cnt + b.cnt;
    res.pre = a.pre;
    res.suf = b.suf;
    Add(res.pre,b.pre);
    Add(res.suf,a.suf);
    long long cnt = 0,cnt1 = 0;
    int i = 0,j = 0;
    for (i=a.suf.size()-1; i >= 0;--i)
    {
        while (j < b.pre.size() && __gcd(a.suf[i].F,b.pre[j].F) > 1)
        {
            cnt1 += b.pre[j].S;
            ++j;
        }
        res.cnt += 1ll*cnt1*a.suf[i].S;
    }
    return res;
}
void Build(int l,int r,int id)
{
    if (l == r)
    {
        t[id].pre.pb(mp(a[l],1));
        t[id].suf.pb(mp(a[r],1));
        t[id].cnt = (a[l] != 1);
        return;
    }
    int mid = (l+r) >> 1;
    Build(l,mid,2*id);
    Build(mid+1,r,2*id+1);
    t[id] = Merge(t[2*id],t[2*id+1]);
}
void Update(int l,int r,int id,int pos)
{
    if (l == r)
    {
        t[id].pre[0] = t[id].suf[0] = mp(a[pos],1);
        t[id].cnt = (a[pos] != 1);
        return;
    }
    int mid = (l+r) >> 1;
    if (mid >= pos) Update(l,mid,2*id,pos);
    else Update(mid+1,r,2*id+1,pos);
    t[id] = Merge(t[2*id],t[2*id+1]);
}
Node Get(int l,int r,int id,int u,int v)
{
    if (l > v || r < u)
    {
        Node res;
        res.pre = res.suf = {};
        res.cnt = 0;
        return res;
    }
    if (u <= l && r <= v) return t[id];
    int mid = (l+r) >> 1;
    Node L = Get(l,mid,2*id,u,v);
    Node R = Get(mid+1,r,2*id+1,u,v);
    return Merge(L,R);
}
int main()
{
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    read(n),read(m);
    FOR(i,1,n) read(a[i]);
    Build(1,n,1);
    while (m--)
    {
        int type,x,y;
        read(type),read(x),read(y);
        if (type == 1)
        {
            a[x] = y;
            Update(1,n,1,x);
        }
        else
        {
            Node ans = Get(1,n,1,x,y);
            writeln(ans.cnt);
        }
    }
    return 0;
}

Compilation message

garaza.cpp: In function 'void Add(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
garaza.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; i < y.size();++i)
            ~~^~~~~~~~~~
garaza.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (;i < y.size();++i)
           ~~^~~~~~~~~~
garaza.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (r < y.size() && cur == __gcd(cur,y[r].F))
                ~~^~~~~~~~~~
garaza.cpp: In function 'Node Merge(Node&, Node&)':
garaza.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < b.pre.size() && __gcd(a.suf[i].F,b.pre[j].F) > 1)
                ~~^~~~~~~~~~~~~~
garaza.cpp:55:15: warning: unused variable 'cnt' [-Wunused-variable]
     long long cnt = 0,cnt1 = 0;
               ^~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 22532 KB Output is correct
2 Correct 41 ms 22804 KB Output is correct
3 Correct 63 ms 23432 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 26332 KB Output is correct
2 Correct 323 ms 28388 KB Output is correct
3 Correct 379 ms 28388 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 32172 KB Output is correct
2 Correct 754 ms 32428 KB Output is correct
3 Correct 734 ms 32844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 40004 KB Output is correct
2 Correct 1266 ms 40360 KB Output is correct
3 Correct 1286 ms 40360 KB Output is correct