oj.uz

답안 #368366

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
368366 2021-02-20T01:30:19 Z KoD 말 (IOI15_horses) C++17
100 / 100
 554 ms 57068 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <set>

#ifndef LOCAL
#include "horses.h"
#endif

namespace Solver {
    template <class T>
    using Vec = std::vector<T>;
    using ll = long long;

    constexpr ll MOD = 1000000007;

    ll mod_pow(ll x, ll e) {
        ll ret = 1;
        while (e > 0) {
            if (e & 1) {
                ret *= x;
                ret %= MOD;
            }
            x *= x;
            x %= MOD;
            e >>= 1;
        }
        return ret;
    }

    ll mod_inv(ll x) {
        return mod_pow(x, MOD - 2);
    }

    template <class Monoid>
    struct Segtree { 
        Vec<Monoid> data;
        Segtree() = default;
        Segtree(const int n): data(2 * n, Monoid::zero()) { }
        void fetch(const int k) {
            data[k] = data[k * 2] + data[k * 2 + 1];
        }
        void assign(int i, const Monoid &mn) {
            i += size();
            data[i] = mn;
            while (i > 1) {
                i >>=  1;
                fetch(i);
            }
        }
        Monoid fold(int l, int r) {
            l += size();
            r += size();
            auto sumL = Monoid::zero();
            auto sumR = Monoid::zero();
            while (l < r) {
                if (l & 1) {
                    sumL = sumL + data[l];
                    l += 1;
                }
                if (r & 1) {
                    r -= 1;
                    sumR = data[r] + sumR;
                }
                l >>= 1;
                r >>= 1;
            }
            return sumL + sumR;
        }
        int size() const {
            return (int) data.size() / 2;
        }
    };

    struct Prod {
        static Prod zero() { return Prod { 1 }; }
        ll value;
        Prod operator + (const Prod &other) const {
            ll tmp = value * other.value;
            return Prod { tmp >= MOD ? 0 : tmp };
        }
    };

    struct Max {
        static Max zero() { return Max { 0 }; }
        ll value;
        Max operator + (const Max &other) const {
            return Max { std::max(value, other.value) };
        }
    };

    ll all_prod = 1;
    Segtree<Prod> x_prod;
    Segtree<Max> y_max;
    std::set<int> consider;

    void setx(const int i, const int x) {
        all_prod *= mod_inv(x_prod.fold(i, i + 1).value);
        all_prod %= MOD;
        all_prod *= x;
        all_prod %= MOD;
        x_prod.assign(i, Prod { x });
        if (x == 1) {
            if (i != 0 && i + 1 != (int) x_prod.size()) {
                consider.erase(i);
            }
        }
        if (x >= 2) {
            consider.insert(i);
        }
    }

    void sety(const int i, const int y) {
        y_max.assign(i, Max { y });
    }

    ll fold() {
        ll up = 0, down = 1;
        int last = x_prod.size();
        for (auto itr = consider.rbegin(); itr != consider.rend(); ++itr) {
            const auto i = *itr;
            const auto x = x_prod.fold(i + 1, x_prod.size()).value;
            if (x == 0) {
                break;
            }
            const auto y = y_max.fold(i, last).value;
            if (up * x < down * y) { 
                up = y;
                down = x;
            }
            last = i;
        }
        return (((all_prod * mod_inv(down)) % MOD) * up) % MOD;
    }
}

int init(int N, int X[], int Y[]) {
    using namespace Solver;
    x_prod = Segtree<Prod>(N);
    y_max = Segtree<Max>(N);
    consider.insert(0);
    consider.insert(N - 1);
    for (int i = 0; i < N; ++i) {
        setx(i, X[i]);
        sety(i, Y[i]);
    }
    return fold();
}

int updateX(int pos, int val) {
    using namespace Solver;
    setx(pos, val);
    return fold();
}

int updateY(int pos, int val) {
    using namespace Solver;
    sety(pos, val);
    return fold();
}

#ifdef LOCAL
int main() {
    int N;
    int X[100] = {};
    int Y[100] = {};
    std::cin >> N;
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> Y[i];
    }
    std::cout << init(N, X, Y) << '\n';
    int M;
    std::cin >> M;
    while (M--) {
        int t, p, v;
        std::cin >> t >> p >> v;
        if (t == 1) {
            std::cout << updateX(p, v) << '\n';
        }
        else {
            std::cout << updateY(p, v) << '\n';
        }
    }
    return 0;
}
#endif

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:149:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  149 |     return fold();
      |            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:155:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  155 |     return fold();
      |            ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:161:16: warning: conversion from 'Solver::ll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  161 |     return fold();
      |            ~~~~^~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 364 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 0 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 2 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 387 ms 44396 KB Output is correct
2 Correct 476 ms 44396 KB Output is correct
3 Correct 429 ms 48272 KB Output is correct
4 Correct 518 ms 52076 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 0 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 2 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 3 ms 364 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 2 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 204 ms 24072 KB Output is correct
34 Correct 197 ms 24044 KB Output is correct
35 Correct 342 ms 54380 KB Output is correct
36 Correct 332 ms 54348 KB Output is correct
37 Correct 204 ms 22252 KB Output is correct
38 Correct 278 ms 35076 KB Output is correct
39 Correct 185 ms 21996 KB Output is correct
40 Correct 339 ms 49388 KB Output is correct
41 Correct 192 ms 22124 KB Output is correct
42 Correct 190 ms 22252 KB Output is correct
43 Correct 313 ms 50028 KB Output is correct
44 Correct 314 ms 49900 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 0 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 2 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 2 ms 364 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 2 ms 364 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Correct 2 ms 364 KB Output is correct
30 Correct 2 ms 492 KB Output is correct
31 Correct 2 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 379 ms 48164 KB Output is correct
34 Correct 470 ms 57068 KB Output is correct
35 Correct 436 ms 48236 KB Output is correct
36 Correct 554 ms 52112 KB Output is correct
37 Correct 203 ms 24136 KB Output is correct
38 Correct 193 ms 24044 KB Output is correct
39 Correct 342 ms 54508 KB Output is correct
40 Correct 334 ms 54252 KB Output is correct
41 Correct 202 ms 22252 KB Output is correct
42 Correct 295 ms 34924 KB Output is correct
43 Correct 192 ms 21996 KB Output is correct
44 Correct 326 ms 49372 KB Output is correct
45 Correct 183 ms 21996 KB Output is correct
46 Correct 195 ms 22252 KB Output is correct
47 Correct 308 ms 49964 KB Output is correct
48 Correct 312 ms 49772 KB Output is correct
49 Correct 299 ms 27124 KB Output is correct
50 Correct 279 ms 27248 KB Output is correct
51 Correct 419 ms 56172 KB Output is correct
52 Correct 413 ms 55788 KB Output is correct
53 Correct 399 ms 25452 KB Output is correct
54 Correct 362 ms 39020 KB Output is correct
55 Correct 268 ms 23148 KB Output is correct
56 Correct 408 ms 51308 KB Output is correct
57 Correct 259 ms 23788 KB Output is correct
58 Correct 298 ms 24300 KB Output is correct
59 Correct 314 ms 49900 KB Output is correct