Submission #792150

#	Time	Username	Problem	Language	Result	Execution time	Memory
792150		Nhoksocqt1	Garaža (COCI17_garaza)	C++17	80 / 160	4057 ms	9432 KiB

garaza

#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 walkOnSeg(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 = walkOnSeg(id << 1 | 1, mid + 1, r, u, v, k);
    if(qr > mid + 1)
        return qr;

    return min(qr, walkOnSeg(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];
    }

    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;
        if(type == 1) {
            update1(L, R);
            a[(x = L)] = R;
            int gcdNow(a[x]);
            while(x > 0 && gcdNow > 1) {
                int l(1), r(x - 1), opt(x);
                while(l <= r) {
                    int mid = (l + r) >> 1;
                    if(query1(1, 1, nArr, mid, x) == gcdNow) {
                        opt = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }

                int tmp(opt);
                l = L + 1, r = nArr, opt = L;
                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;
                    }
                }

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

            if(x > 0) {
                int pos = walkOnSeg(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 = walkOnSeg(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 / 40
• Subtask 2: 40 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40