oj.uz

Submission #792341

# Submission time Handle Problem Language Result Execution time Memory
792341 2023-07-25T01:45:46 Z Nhoksocqt1 Garaža (COCI17_garaza) C++17
160 / 160
 610 ms 9696 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

struct Node {
    ll sum;
    int minv, lz;
} seg2[4 * MAXN];

int a[MAXN], b[MAXN], seg[4 * MAXN], posInTree[MAXN], nArr, numQuery;

void build(int id, int l, int r) {
    if(l == r) {
        posInTree[l] = id;
        seg[id] = a[l];
        seg2[id] = {b[l], b[l], -1};
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    seg[id] = __gcd(seg[id << 1], seg[id << 1 | 1]);
    seg2[id] = {seg2[id << 1].sum + seg2[id << 1 | 1].sum, min(seg2[id << 1].minv, seg2[id << 1 | 1].minv), -1};
}

void update1(int pos, int val) {
    int id(posInTree[pos]);
    seg[id] = val;
    while(id > 1) {
        id >>= 1;
        seg[id] = __gcd(seg[id << 1], seg[id << 1 | 1]);
    }
}

int query1(int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 0;

    if(u <= l && r <= v)
        return seg[id];

    int mid = (l + r) >> 1;
    return __gcd(query1(id << 1, l, mid, u, v), query1(id << 1 | 1, mid + 1, r, u, v));
}

void inline pushDown(int id, int l, int r) {
    int &lz(seg2[id].lz), mid = (l + r) >> 1;
    seg2[id << 1] = {1LL * (mid - l + 1) * lz, lz, lz};
    seg2[id << 1 | 1] = {1LL * (r - mid) * lz, lz, lz};

    lz = -1;
}

void update2(int id, int l, int r, int u, int v, int k) {
    if(v < l || u > r)
        return;

    if(u <= l && r <= v) {
        seg2[id] = {1LL * (r - l + 1) * k, k, k};
        return;
    }

    if(seg2[id].lz != -1)
        pushDown(id, l, r);

    int mid = (l + r) >> 1;
    update2(id << 1, l, mid, u, v, k);
    update2(id << 1 | 1, mid + 1, r, u, v, k);
    seg2[id] = {seg2[id << 1].sum + seg2[id << 1 | 1].sum, min(seg2[id << 1].minv, seg2[id << 1 | 1].minv), -1};
}

ll query2(int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return 0;

    if(u <= l && r <= v)
        return seg2[id].sum;

    if(seg2[id].lz != -1)
        pushDown(id, l, r);

    int mid = (l + r) >> 1;
    return query2(id << 1, l, mid, u, v) + query2(id << 1 | 1, mid + 1, r, u, v);
}

int findFirst(int id, int l, int r, int u, int v, int k) {
    if(v < l || u > r)
        return v + 1;

    if(u <= l && r <= v) {
        while(l < r) {
            int mid = (l + r) >> 1;
            if(seg[id << 1 | 1] % k == 0) {
                id = id << 1;
                r = mid;
            } else {
                id = id << 1 | 1;
                l = mid + 1;
            }
        }

        return (seg[id] % k == 0) ? l : l + 1;
    }

    int mid = (l + r) >> 1;
    int qr = findFirst(id << 1 | 1, mid + 1, r, u, v, k);
    if(qr > mid + 1)
        return qr;

    return min(qr, findFirst(id << 1, l, mid, u, v, k));
}

int gn;
int findLast(int id, int l, int r, int u, int v) {
    if(v < l || u > r)
        return u - 1;

    if(u <= l && r <= v) {
        while(l < r) {
            int mid = (l + r) >> 1;
            if(__gcd(seg[id << 1], gn) > 1) {
                gn = __gcd(gn, seg[id << 1]);
                id = id << 1 | 1;
                l = mid + 1;
            } else {
                id = id << 1;
                r = mid;
            }
        }

        if(__gcd(seg[id], gn) > 1) {
            gn = __gcd(gn, seg[id]);
            return l;
        } else {
            return l - 1;
        }
    }

    int mid = (l + r) >> 1;
    int qr = findLast(id << 1, l, mid, u, v);
    if(qr < mid)
        return qr;

    return findLast(id << 1 | 1, mid + 1, r, u, v);
}

int walkOnSeg2(int id, int l, int r, int u, int v, int k) {
    if(v < l || u > r)
        return v + 1;

    if(u <= l && r <= v) {
        while(l < r) {
            if(seg2[id].lz != -1)
                pushDown(id, l, r);

            int mid = (l + r) >> 1;
            if(seg2[id << 1 | 1].minv >= k) {
                id = id << 1;
                r = mid;
            } else {
                id = id << 1 | 1;
                l = mid + 1;
            }
        }

        return (seg2[id].minv >= k) ? l : l + 1;
    }

    if(seg2[id].lz != -1)
        pushDown(id, l, r);

    int mid = (l + r) >> 1;
    int qr = walkOnSeg2(id << 1 | 1, mid + 1, r, u, v, k);
    if(qr > mid + 1)
        return qr;

    return min(qr, walkOnSeg2(id << 1, l, mid, u, v, k));
}

inline ll C2(int n) {
    return 1LL * n * (n + 1) / 2;
}

void process() {
    cin >> nArr >> numQuery;
    for (int i = 1; i <= nArr; ++i) {
        cin >> a[i];
        //a[i] = Random(1, 100); cout << a[i] << " \n"[i == nArr];
    }

    build(1, 1, nArr);
    for (int i = 1; i <= nArr; ++i) {
        b[i] = i - 1;
        if(a[i] == 1)
            continue;

        int l(i + 1), r(nArr), opt(i);
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(query1(1, 1, nArr, i, mid) > 1) {
                opt = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        b[i] = opt;
    }

    build(1, 1, nArr);
    for (int t = 0; t < numQuery; ++t) {
        int type, L, R, x;
        cin >> type >> L >> R;
        //type = Random(1, 2), L = Random(1, nArr), R = (type == 1 ? Random(1, 100) : Random(L, nArr)); cout << type << ' ' << L << ' ' << R << '\n';

        if(type == 1) {
            update1(L, R);
            a[(x = L)] = R;
            int gcdNow(a[x]);
            while(x > 0 && gcdNow > 1) {
                int opt = findFirst(1, 1, nArr, 1, x, gcdNow), tmp(opt);

                /*opt = L;
                int l(L + 1), r(nArr);
                while(l <= r) {
                    int mid = (l + r) >> 1;
                    if(query1(1, 1, nArr, tmp, mid) > 1) {
                        opt = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }*/

                //gn = 0; cout << '.' << tmp << ' ' << opt << ' ' << findLast(1, 1, nArr, tmp, nArr) << '\n';
                //gn = 0; if(findLast(1, 1, nArr, tmp, nArr) != opt) exit(1);
                gn = 0; opt = findLast(1, 1, nArr, tmp, nArr);
                update2(1, 1, nArr, tmp, x, opt);
                x = tmp - 1;
                if(x > 0)
                    gcdNow = __gcd(gcdNow, a[x]);
            }

            if(x > 0) {
                int pos = walkOnSeg2(1, 1, nArr, 1, x, L);
                //cout << '.' << pos << ' ' << x << ' ' << L - 1 << '\n';
                if(pos <= x)
                    update2(1, 1, nArr, pos, x, L - 1);
            }
        } else {
            ll result(0);
            int pos = walkOnSeg2(1, 1, nArr, L, R, R);
            //cout << L << ' ' << R << ' ' << pos << '\n';
            if(pos <= R)
                result += 1LL * (R - pos + 1) * (R + 1) - (C2(R) - C2(pos - 1));

            if(L < pos)
                result += query2(1, 1, nArr, L, pos - 1) - (C2(pos - 1) - C2(L - 1)) + (pos - L);

            cout << result << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 11 ms 604 KB Output is correct
3 Correct 20 ms 844 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 2388 KB Output is correct
2 Correct 125 ms 2776 KB Output is correct
3 Correct 115 ms 2788 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 4712 KB Output is correct
2 Correct 278 ms 5356 KB Output is correct
3 Correct 250 ms 5196 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 9432 KB Output is correct
2 Correct 610 ms 9696 KB Output is correct
3 Correct 474 ms 9348 KB Output is correct