제출 #61690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61690		win11905	Garaža (COCI17_garaza)	C++11	160 / 160	1840 ms	42036 KiB

garaza

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

#define long long long
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second

const int N = 1<<17;

int n, m, A[N];
long t[N<<1];
vector<pii> pref[N<<1], suff[N<<1];

long getMerge(vector<pii> &L, vector<pii> &R, int l, int r, int m) {
    long sum = 0;
    for(int i = 0, j = L.size()-1; i < R.size(); ++i) {
        while(j >= 0 && __gcd(L[j].x, R[i].x) == 1) j--;
        if(j < 0) continue;
        long ret = m - (j < L.size()-1 ? L[j+1].y : l-1);
        ret *= (i < R.size()-1 ? R[i+1].y : r+1) - R[i].y;
        sum += ret; 
    }
    return sum;
}

vector<pii> Merge(vector<pii> &L, vector<pii> &R) {
    vector<pii> ret = L;
    for(int i = 0; i < R.size(); ++i) {
        int gcd = __gcd(L.back().x, R[i].x);
        if(gcd != ret.back().x) ret.emplace_back(gcd, R[i].y);
    }
    return ret;
}

void MergeAll(int p, int l, int r) {
    int m = l + r >> 1;
    t[p] = t[p<<1] + t[p<<1|1] + getMerge(suff[p<<1], pref[p<<1|1], l, r, m);
    pref[p] = Merge(pref[p<<1], pref[p<<1|1]);
    suff[p] = Merge(suff[p<<1|1], suff[p<<1]);
}

void build(int p = 1, int l = 1, int r = n) {
    if(l == r) {
        scanf("%d", A+l);
        pref[p].emplace_back(A[l], l);
        suff[p].emplace_back(A[r], r);
        t[p] = A[l] > 1;
        return;
    }
    int m = l + r >> 1;
    build(p<<1, l, m), build(p<<1|1, m+1, r);
    MergeAll(p, l, r);
}

void update(int x, int v, int p = 1, int l = 1, int r = n) {
    if(l == r) {
        pref[p][0] = suff[p][0] = pii(A[l] = v, r);
        t[p] = A[l] > 1;
        return;
    }
    int m = l + r >> 1;
    if(x <= m) update(x, v, p<<1, l, m);
    else update(x, v, p<<1|1, m+1, r);
    MergeAll(p, l, r);
}

vector<iii> query(int x, int y, int p = 1, int l = 1, int r = n) {
    if(x > r || l > y) return vector<iii>();
    if(x <= l && r <= y) return vector<iii>(1, make_tuple(p, l, r));
    int m = l + r >> 1;
    vector<iii> ret = query(x, y, p<<1, l, m);
    for(auto x : query(x, y, p<<1|1, m+1, r)) ret.emplace_back(x);
    return ret;
}

long get(int x, int y) {
    vector<iii> ret = query(x, y);
    vector<pii> rsuff;
    long sum = 0;
    int p, l, r;
    for(auto x : ret) {
        tie(p, l, r) = x;
        sum += t[p] + getMerge(rsuff, pref[p], get<1>(ret[0]), r, l-1);
        rsuff = Merge(suff[p], rsuff);
    }
    return sum;
}

int main() {
    scanf("%d %d", &n, &m);
    build();
    for(int i = 0, a, b, c; i < m; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        if(a == 1) update(b, c);
        else printf("%lld\n", get(b, c));
    }
}

컴파일 시 표준 에러 (stderr) 메시지

garaza.cpp: In function 'long long int getMerge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&, int, int, int)':
garaza.cpp:18:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0, j = L.size()-1; i < R.size(); ++i) {
                                    ~~^~~~~~~~~~
garaza.cpp:21:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         long ret = m - (j < L.size()-1 ? L[j+1].y : l-1);
                         ~~^~~~~~~~~~~~
garaza.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ret *= (i < R.size()-1 ? R[i+1].y : r+1) - R[i].y;
                 ~~^~~~~~~~~~~~
garaza.cpp: In function 'std::vector<std::pair<int, int> > Merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
garaza.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < R.size(); ++i) {
                    ~~^~~~~~~~~~
garaza.cpp: In function 'void MergeAll(int, int, int)':
garaza.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
garaza.cpp: In function 'void build(int, int, int)':
garaza.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
garaza.cpp: In function 'void update(int, int, int, int, int)':
garaza.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
garaza.cpp: In function 'std::vector<std::tuple<int, int, int> > query(int, int, int, int, int)':
garaza.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
garaza.cpp: In function 'void build(int, int, int)':
garaza.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+l);
         ~~~~~^~~~~~~~~~~
garaza.cpp: In function 'int main()':
garaza.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
garaza.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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