제출 #640804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640804		piOOE	말 (IOI15_horses)	C++17	100 / 100	550 ms	48936 KiB

horses

#include <bits/stdc++.h>
#include "horses.h"

using namespace std;
using ll = long long;

constexpr int MOD = 1e9 + 7;

int add(int a, int b) {
    return a + b < MOD ? a + b : a + b - MOD;
}

int mul(int a, int b) {
    return (long long) a * b % MOD;
}

int sub(int a, int b) {
    return a >= b ? a - b : a - b + MOD;
}

int power(int a, int b) {
    int ans = 1;
    for (; b > 0; b >>= 1, a = mul(a, a)) if (b & 1) ans = mul(ans, a);
    return ans;
}

int inv(int a) {
    return power(a, MOD - 2);
}

vector<int> t;
int sz = 1;

void init(vector<int> a) {
    sz = 1;
    while (sz < a.size()) sz <<= 1;
    t.assign(sz << 1, 0);
    for (int i = 0; i < a.size(); ++i) {
        t[i + sz] = a[i];
    }
    for (int i = sz - 1; i > 0; --i) {
        t[i] = max(t[i << 1], t[i << 1 | 1]);
    }
}

void pull(int x) {
    t[x] = max(t[x << 1], t[x << 1 | 1]);
}

void modify(int i, int val, int x = 1, int lx = 0, int rx = sz) {
    if (lx + 1 == rx) {
        t[x] = val;
        return;
    }
    int mid = (lx + rx) >> 1;
    if (i < mid) modify(i, val, x << 1, lx, mid);
    else modify(i, val, x << 1 | 1, mid, rx);
    pull(x);
}

int query(int l, int r, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx ||  lx >= r) return 0;
    if (l <= lx && rx <= r) return t[x];
    int mid = (lx + rx) >> 1;
    return max(query(l, r, x << 1, lx, mid), query(l, r, x << 1 | 1, mid, rx));
}

int n;

vector<int> x, y;

int prodX = 1;

set<int> alive;

int answer() {
    int maxY = t[1];
    if (alive.empty()) {
        return maxY;
    }
    vector<int> pos;
    ll m = 1;
    auto it = alive.end();
    do {
        it = prev(it);
        m *= x[*it];
    } while (m <= maxY && it != alive.begin());
    if (m <= maxY) {
        vector<int> consider;
        for (int i : alive) consider.push_back(i);
        if (consider[0] != 0) {
            consider.insert(consider.begin(), 0);
        }
        ll prod = 1;
        ll ans = 1;
        consider.push_back(n);
        for (int i = 0; i < (int) consider.size() - 1; ++i) {
            int j = consider[i];
            prod *= x[j];
            ans = max(ans, prod * query(j, consider[i + 1]));
        }
        return ans % MOD;
    }
    ll ans = 1;
    auto itt = it;
    int newProd = mul(prodX, inv(m / x[*it]));
    for (m = 1; it != alive.end(); it = next(it)) {
        if (it != itt) {
            m *= x[*it];
        }
        ans = max(ans, m * query(*it, n));
    }
    ans %= MOD;
    return mul(newProd, ans);
}

int init(int N, int X[], int Y[]) {
    n = N;
    x.resize(n), y.resize(n);
    for (int i = 0; i < n; ++i) {
        x[i] = X[i], y[i] = Y[i];
        if (x[i] != 1) {
            prodX = mul(prodX, x[i]);
            alive.insert(alive.end(), i);
        }
    }
    init(y);
    return answer();
}

int updateX(int pos, int val) {
    prodX = mul(prodX, inv(x[pos]));
    x[pos] = val;
    prodX = mul(prodX, val);
    if (val == 1) {
        alive.erase(pos);
    } else {
        alive.insert(pos);
    }
    return answer();
}


int updateY(int pos, int val) {
    y[pos] = val;
    modify(pos, val);
    return answer();
}

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

horses.cpp: In function 'int mul(int, int)':
horses.cpp:14:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   14 |     return (long long) a * b % MOD;
      |            ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'void init(std::vector<int>)':
horses.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while (sz < a.size()) sz <<= 1;
      |            ~~~^~~~~~~~~~
horses.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < a.size(); ++i) {
      |                     ~~^~~~~~~~~~
horses.cpp: In function 'int answer()':
horses.cpp:102:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |         return ans % MOD;
      |                ~~~~^~~~~
horses.cpp:106:36: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  106 |     int newProd = mul(prodX, inv(m / x[*it]));
horses.cpp:114:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  114 |     return mul(newProd, ans);
      |                         ^~~

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