oj.uz

답안 #52823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52823 2018-06-27T01:35:41 Z EntityIT Garaža (COCI17_garaza) C++14
0 / 160
 1696 ms 46560 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
typedef pair<int, int> ii;

const int N = 1e5 + 5;
int n, q, a[N];
struct node {
    vector<ii> l, r;
    int cnt;
    node () : cnt(0) {}
    node (int val) {
        cnt = (val != 1);
        l.clear(); r.clear();
        l.push_back(ii(val, 1) ); r.push_back(ii(val, 1) );
    }
    void add (vector<ii> &_res, vector<ii> _rem) {
        if (!_res.size()) return ;
        for (auto pa : _rem) {
            if (pa.fi % _res.back().fi == 0) _res.back().se = _res.back().se + pa.se;
            else _res.push_back(ii(__gcd(pa.fi, _res.back().fi), _res.back().se + pa.se) );
        }
    }
    node operator+(const node& rem) {
        node res;
        res.cnt = cnt + rem.cnt;
        res.l = l; res.r = rem.r;
        add (res.l, rem.l); add (res.r, r);
        int pter = rem.l.size() - 1;
        for (int i = 0; i < r.size(); ++i) {
            while (pter >= 0 && __gcd (r[i].fi, rem.l[pter].fi) == 1 ) pter--;
            if (pter >= 0) res.cnt += rem.l[pter].se * ( r[i].se - (i ? r[i - 1].se : 0) );
        }
        return res;
    }
};

struct SegmentTree {
    node v[4 * N];
    void build_tree (int i, int left, int right) {
        if (left > right) return ;
        if (left == right) {
            v[i] = node(a[left]);
            return ;
        }
        int mid = (left + right) >> 1;
        build_tree(i << 1, left, mid); build_tree(i << 1 | 1, mid + 1, right);
        v[i] = v[i << 1] + v[i << 1 | 1];
    }
    void update(int i, int left, int right, int pos, int val) {
        if (left > right || right < pos || pos < left) return ;
        if (left == right) {
            v[i] = node (val); return ;
        }
        int mid = (left + right) >> 1;
        update(i << 1, left, mid, pos, val); update(i << 1 | 1, mid + 1, right, pos, val);
        v[i] = v[i << 1] + v[i << 1 | 1];
    }
    node get(int i, int left, int right, int l, int r) {
        if (left > right || right < l || r < left) return node();
        if (l <= left && right <= r) return v[i];
        int mid = (left + right) >> 1;
        return get(i << 1, left, mid, l, r) + get(i << 1 | 1, mid + 1, right, l, r);
    }
} it;

signed main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    it.build_tree(1, 1, n);
    while (q--) {
        int type, x, v; cin >> type >> x >> v;
        if (type == 1) it.update(1, 1, n, x, v);
        else cout << it.get(1, 1, n, x, v).cnt << '\n';
    }

    return 0;
}

Compilation message

garaza.cpp: In member function 'node node::operator+(const node&)':
garaza.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < r.size(); ++i) {
                         ~~^~~~~~~~~~

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 22492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 389 ms 27036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 979 ms 34008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1696 ms 46560 KB Output isn't correct
2 Halted 0 ms 0 KB -