답안 #24115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
24115	2017-05-31T09:01:30 Z	Nirjhor	말 (IOI15_horses)	C++14	컴파일 오류	0 ms	0 KB

horses

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef long double ld;

const ld EPS = 1e-9;
const int N = 5e5 + 10;
const int MOD = 1e9 + 7;

int n, m;
ll x[N], y[N];
int tree[4 * N];
ld xlog[N], ylog[N];
ll product[N + N];
ld logsum[N + N];

void init_product (void) {
    for (int i = 0; i < n; ++i) {
        product[n + i] = x[i] % MOD;
    }
    for (int i = n - 1; i; --i) {
        product[i] = (product[i << 1] * product[i << 1 | 1]) % MOD;
    }
}

void modify_product (int p, ll v) {
    for (product[p += n] = v; p > 1; p >>= 1) {
        product[p >> 1] = (product[p] * product[p ^ 1]) % MOD;
    }
}

ll find_product (int l, int r) {
    ll ret = 1LL;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ret *= product[l++], ret %= MOD;
        if (r & 1) ret *= product[--r], ret %= MOD;
    }
    return ret;
}

void init_logsum (void) {
    for (int i = 0; i < n; ++i) {
        logsum[n + i] = xlog[i];
    }
    for (int i = n - 1; i; --i) {
        logsum[i] = logsum[i << 1] + logsum[i << 1 | 1];
    }
}

void modify_logsum (int p, ld v) {
    for (logsum[p += n] = v; p > 1; p >>= 1) {
        logsum[p >> 1] = logsum[p] + logsum[p ^ 1];
    }
}

ld find_logsum (int l, int r) {
    ld ret = 0.0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ret += logsum[l++];
        if (r & 1) ret += logsum[--r];
    }
    return ret;
}

int merged (int p, int q) {
    if (p > q) swap(p, q);
    return (find_logsum(p + 1, q + 1) - ylog[p] + ylog[q] > -EPS) ? q : p;
}

void init_tree (int u, int b, int e) {
    if (b == e) {
        tree[u] = b;
        return;
    }
    int l = u << 1, r = l | 1, m = b + e >> 1;
    init_tree(l, b, m), init_tree(r, m + 1, e);
    tree[u] = merged(tree[l], tree[r]);
}

void modify_tree (int u, int b, int e, int p) {
    if (b > p or e < p) return;
    if (b == e) return;
    int l = u << 1, r = l | 1, m = b + e >> 1;
    modify_tree(l, b, m, p), modify_tree(r, m + 1, e, p);
    tree[u] = merged(tree[l], tree[r]);
}

ll value (int index) {
    return (find_product(0, index + 1) * y[index]) % MOD;
}

int main (int argc, char const *argv[]) {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", x + i);
        xlog[i] = log(x[i]);
    }
    for (int i = 0; i < n; ++i) {
        scanf("%lld", y + i);
        ylog[i] = log(y[i]);
    }
    init_product();
    init_logsum();
    init_tree(1, 0, n - 1);
    printf("%lld\n", value(tree[1]));
    scanf("%d", &m); while (m--) {
        int cmd, pos; ll val;
        scanf("%d %d %lld", &cmd, &pos, &val);
        if (cmd == 1) {
            x[pos] = val, xlog[pos] = log(val);
            modify_product(pos, x[pos]);
            modify_logsum(pos, xlog[pos]);
            modify_tree(1, 0, n - 1, pos);
        } else {
            y[pos] = val, ylog[pos] = log(val);
            modify_tree(1, 0, n - 1, pos);
        }
        printf("%lld\n", value(tree[1]));
    }
    return 0;  
}

Compilation message

horses.cpp: In function 'void init_tree(int, int, int)':
horses.cpp:77:32: warning: declaration of 'm' shadows a global declaration [-Wshadow]
     int l = u << 1, r = l | 1, m = b + e >> 1;
                                ^
horses.cpp:12:8: note: shadowed declaration is here
 int n, m;
        ^
horses.cpp:77:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int l = u << 1, r = l | 1, m = b + e >> 1;
                                      ^
horses.cpp: In function 'void modify_tree(int, int, int, int)':
horses.cpp:85:32: warning: declaration of 'm' shadows a global declaration [-Wshadow]
     int l = u << 1, r = l | 1, m = b + e >> 1;
                                ^
horses.cpp:12:8: note: shadowed declaration is here
 int n, m;
        ^
horses.cpp:85:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int l = u << 1, r = l | 1, m = b + e >> 1;
                                      ^
horses.cpp: At global scope:
horses.cpp:94:15: warning: unused parameter 'argc' [-Wunused-parameter]
 int main (int argc, char const *argv[]) {
               ^
horses.cpp:94:38: warning: unused parameter 'argv' [-Wunused-parameter]
 int main (int argc, char const *argv[]) {
                                      ^
horses.cpp: In function 'int main(int, const char**)':
horses.cpp:95:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
horses.cpp:97:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", x + i);
                             ^
horses.cpp:101:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", y + i);
                             ^
horses.cpp:108:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m); while (m--) {
                    ^
horses.cpp:110:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &cmd, &pos, &val);
                                              ^
/tmp/ccR5s6yg.o: In function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'
/tmp/cc9J9LOJ.o:horses.cpp:(.text.startup+0x0): first defined here
/tmp/ccR5s6yg.o: In function `main':
grader.c:(.text.startup+0x282): undefined reference to `init(int, int*, int*)'
grader.c:(.text.startup+0x75e): undefined reference to `updateX(int, int)'
grader.c:(.text.startup+0xae1): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status