Submission #1205640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205640		CodeLakVN	Garaža (COCI17_garaza)	C++20	0 / 160	237 ms	9456 KiB

garaza

#include <bits/stdc++.h>
using namespace std;

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)1e5 + 5;

int n, q;
int a[MAX_N], f[MAX_N];

struct GCD_IT {
    int tree[4 * MAX_N];

    void build(int id, int l, int r) {
        if (l == r) {
            tree[id] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        tree[id] = __gcd(tree[2 * id], tree[2 * id + 1]);
    } 

    void update(int id, int l, int r, int pos) {
        if (l == r) {
            tree[id] = a[pos];
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(2 * id, l, mid, pos);
        else update(2 * id + 1, mid + 1, r, pos);
        tree[id] = __gcd(tree[2 * id], tree[2 * id + 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        if (r < u || l > v) return 0;
        if (l >= u && r <= v) return tree[id];
        int mid = (l + r) >> 1;
        return __gcd(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
    }

    // find maximum position j such that gcd(pos..j) > 1
    int walkRight(int id, int l, int r, int pos, int num) { 
        if (r < pos) return num;
        if (l >= pos) {
            if (__gcd(tree[id], num) > 1) return __gcd(tree[id], num);
            while (l != r) {
                int mid = (l + r) >> 1;
                if (__gcd(tree[2 * id], num) > 1) {
                    num = __gcd(tree[2 * id], num);
                    id = 2 * id + 1;
                    l = mid + 1;
                }
                else {
                    id = 2 * id;
                    r = mid;
                }
            }
            return -(l - 1);
        }
        int mid = (l + r) >> 1;
        int res = walkRight(2 * id, l, mid, pos, num);
        if (res <= 0) return res;
        num = __gcd(num, res);
        return walkRight(2 * id + 1, mid + 1, r, pos, num);
    }

    // find the leftmost position j such that gcd(j..pos) == num
    int walkLeft(int id, int l, int r, int pos, int num) {
        if (l > pos) return -1;
        if (r <= pos) {
            if (__gcd(tree[id], num) == num) return -1;
            while (l != r) {
                int mid = (l + r) >> 1;
                if (__gcd(tree[2 * id + 1], num) == num) {
                    id = 2 * id;
                    r = mid;
                }
                else {
                    id = 2 * id + 1;
                    l = mid + 1;
                }
            }
            return l;
        }
        int mid = (l + r) >> 1;
        int res = walkLeft(2 * id + 1, mid + 1, r, pos, num);
        if (res >= 0) return res;
        return walkLeft(2 * id, l, mid, pos, num);
    }
} gcdTree;

struct IT {
    struct NODE {
        int val, lazy;
        long long sum;

        NODE() {
            val = sum = 0;
            lazy = -1;
        }

        void apply(int num, int l, int r) {
            if (num == -1) return;
            val = lazy = num;
            sum = 1LL * (r - l + 1) * val;
        }
    } tree[4 * MAX_N];

    NODE combine(NODE A, NODE B) {
        NODE res;
        res.sum = A.sum + B.sum;
        res.val = B.val;
        return res;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            tree[id].val = tree[id].sum = f[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
    }

    void down(int id, int l, int r) {
        int mid = (l + r) >> 1;
        tree[2 * id].apply(tree[id].lazy, l, mid);
        tree[2 * id + 1].apply(tree[id].lazy, mid + 1, r);
        tree[id].lazy = -1;
    }

    void update(int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            tree[id].apply(val, l, r);
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(2 * id, l, mid, u, v, val);
        update(2 * id + 1, mid + 1, r, u, v, val);
        tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
    }

    long long get(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return tree[id].sum;
        down(id, l, r);
        int mid = (l + r) >> 1;
        return get(2 * id, l, mid, u, v) + get(2 * id + 1, mid + 1, r, u, v);
    }

    // find nearest position j such that f[j] >= val
    int walk(int id, int l, int r, int val) {
        if (l == r) {
            if (tree[id].val >= val) return l;
            return l + 1;
        }
        int mid = (l + r) >> 1;
        if (tree[2 * id].val >= val) return walk(2 * id, l, mid, val);
        return walk(2 * id + 1, mid + 1, r, val);
    }
} resTree;

long long getSum(int l, int r) {
    if (l > r) return 0;
    return 1LL * (r - l + 1) * (r + l) / 2;
}

void solve() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

    gcdTree.build(1, 1, n);
    FOR(i, 1, n) {
        f[i] = gcdTree.walkRight(1, 1, n, i, a[i]);
        if (f[i] <= 0) f[i] = -f[i];
        else f[i] = n;
    }

    resTree.build(1, 1, n);

    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            a[x] = y;
            gcdTree.update(1, 1, n, x);
            if (y == 1) {
                resTree.update(1, 1, n, x, x, x);
                int L = resTree.walk(1, 1, n, x);
                resTree.update(1, 1, n, L, x, x - 1);
                continue;
            }
            int R = x;
            while (R > 0 && gcdTree.get(1, 1, n, R, x) > 1) {
                int L = gcdTree.walkLeft(1, 1, n, R, gcdTree.get(1, 1, n, R, x));
                if (L < 0) L = 0;
                int rightmost = gcdTree.walkRight(1, 1, n, R, a[R]);
                if (rightmost <= 0) rightmost = -rightmost;
                else rightmost = n;
                resTree.update(1, 1, n, L + 1, R, rightmost);
                R = L;
            }
            if (R > 0) {
                int L = resTree.walk(1, 1, n, x);
                if (L <= R) resTree.update(1, 1, n, L, R, x - 1);
            }
        }
        else {
            int pos = max(x, resTree.walk(1, 1, n, y));
            cout << resTree.get(1, 1, n, x, pos - 1) - getSum(x - 1, pos - 2) + getSum(1, y - pos + 1) << "\n";
        }
    }
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

garaza.cpp: In function 'int32_t main()':
garaza.cpp:235:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  235 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:236:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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