Submission #217718

#	Time	Username	Problem	Language	Result	Execution time	Memory
217718		quocnguyen1012	Garaža (COCI17_garaza)	C++14	160 / 160	900 ms	40536 KiB

garaza

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;
 
int gcd(int x, int y)
{
    while (y)
    {
        x %= y;
        swap(x, y);
    }
    return x;
}
 
int n, qq;
int a[N];
 
struct ban
{
    vector<pair<int, int> > l, r;
    long long ans;
    ban(){}
    ban(int x)
    {
        l.push_back(m_p(x, 1));
        r.push_back(m_p(x, 1));
        if (x > 1)
            ans = 1;
        else
            ans = 0;
    }
};
 
int p[33];
ban mer(const ban& l, const ban& r)
{
    ban res;
    res.l = l.l;
    for (int i = 0; i < r.l.size(); ++i)
    {
        int g = gcd(res.l.back().first, r.l[i].first);
        if (g == res.l.back().first)
            res.l.back().second += r.l[i].second;
        else
            res.l.push_back(m_p(g, r.l[i].second));
    }
    res.r = r.r;
    for (int i = 0; i < l.r.size(); ++i)
    {
        int g = gcd(res.r.back().first, l.r[i].first);
        if (g == res.r.back().first)
            res.r.back().second += l.r[i].second;
        else
            res.r.push_back(m_p(g, l.r[i].second));
    }
    res.ans = l.ans + r.ans;
    p[0] = r.l[0].second;
    for (int i = 1; i < r.l.size(); ++i)
        p[i] = p[i - 1] + r.l[i].second;
    int j = r.l.size() - 1;
    for (int i = 0; i < l.r.size(); ++i)
    {
        while (1)
        {
            if (j == -1)
                break;
            int g = gcd(l.r[i].first, r.l[j].first);
            if (g == 1)
                --j;
            else
                break;
        }
        if (j == -1)
            break;
        res.ans += (l.r[i].second * 1LL * p[j]);
    }
    return res;
}
 
ban t[N * 4];
 
void bil(int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(a[tl]);
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
 
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(y);
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
 
ban qry(int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qry(tl, m, l, r, pos * 2);
    if (l > m)
        return qry(m + 1, tr, l, r, pos * 2 + 1);
    return mer(qry(tl, m, l, m, pos * 2),
               qry(m + 1, tr, m + 1, r, pos * 2 + 1));
}
 
int main()
{
    scanf("%d%d", &n, &qq);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    bil(1, n, 1);
    while (qq--)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ubd(1, n, x, y, 1);
        }
        else
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", qry(1, n, l, r, 1).ans);
        }
    }
    return 0;
}

Compilation message (stderr)

garaza.cpp: In function 'ban mer(const ban&, const ban&)':
garaza.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < r.l.size(); ++i)
                     ~~^~~~~~~~~~~~
garaza.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < l.r.size(); ++i)
                     ~~^~~~~~~~~~~~
garaza.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < r.l.size(); ++i)
                     ~~^~~~~~~~~~~~
garaza.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < l.r.size(); ++i)
                     ~~^~~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~
garaza.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
garaza.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
garaza.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
garaza.cpp:143:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &l, &r);
             ~~~~~^~~~~~~~~~~~~~~~

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