제출 #432516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432516		2qbingxuan	말 (IOI15_horses)	C++14	34 / 100	1598 ms	43412 KiB

horses

#pragma GCC optimize("Ofast")
#include "horses.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ..., (std::cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using ld = long double;
using ll = long long;
using namespace std;
const int maxn = 500025;
const int mod = 1000000007;

struct Segtree {
    pair<ld,int> st[maxn * 2];
    // ld lz[maxn];
    int n;
    void build(int N) {
        n = N;
    }
    void add(int l, int r, ld x) {
        for (int i = l; i < r; i++) st[i+n].first += x;
    }
    int query() {
        pair<ld,int> r;
        for (int i = 0; i < n; i++) {
            r = max(r, st[i + n]);
        }
        return r.second;
    }
} sgt;

ll modpow(ll e, ll p) {
    ll r = 1;
    while (p) {
        if (p&1) r = r*e%mod;
        e = e*e%mod;
        p >>= 1;
    }
    return r;
}
struct Fenwick {
    int n;
    ll b[maxn];
    void init(int N) {
        n = N;
        for (int i = 1; i <= n; i++) b[i] = 1;
    }
    void add(int p, ll d) {
        for (++p; p <= n; p += p&-p) b[p] = b[p] * d % mod;
    }
    ll query(int p) {
        ll r = 1;
        for (++p; p > 0; p -= p&-p) r = r * b[p] % mod;
        return r;
    }
} BIT;
int x[maxn], y[maxn], n;
int init(int N, int X[], int Y[]) {
    long double sum = 0;
    ll prod = 1;
    BIT.init(N);
    for (int i = 0; i < N; i++) {
        sum += log(X[i]);
        prod = prod * X[i] % mod;
        sgt.st[i + N] = { sum + log(Y[i]), i };
        BIT.add(i, X[i]);
    }
    sgt.build(N);
    n = N;
    for (int i = 0; i < N; i++) x[i] = X[i];
    for (int i = 0; i < N; i++) y[i] = Y[i];
    int p = sgt.query();
    return BIT.query(p) * y[p] % mod;
}

int updateX(int pos, int val) {	
    sgt.add(pos, n, -log(x[pos]));
    BIT.add(pos, modpow(x[pos], mod-2));
    x[pos] = val;
    sgt.add(pos, n, log(x[pos]));
    BIT.add(pos, x[pos]);
    int p = sgt.query();
    return BIT.query(p) * y[p] % mod;
}

int updateY(int pos, int val) {
    sgt.add(pos, pos+1, -log(y[pos]));
    y[pos] = val;
    sgt.add(pos, pos+1, log(y[pos]));
    int p = sgt.query();
    return BIT.query(p) * y[p] % mod;
}

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

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:91:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   91 |     return BIT.query(p) * y[p] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:101:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  101 |     return BIT.query(p) * y[p] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:109:32: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  109 |     return BIT.query(p) * y[p] % mod;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23