Submission #640381

#	Time	Username	Problem	Language	Result	Execution time	Memory
640381		piOOE	Horses (IOI15_horses)	C++17	100 / 100	460 ms	47152 KiB

horses

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

using namespace std;
using ll = long long;
using i128 = __int128;

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 a * (long long) 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);
}

struct segtreeY {
    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) {
        modify(i, val, 1, 0, sz);
    }

    void modify(int i, int val, int x, int lx, int rx) {
        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) {
        return query(l, r, 1, 0, sz);
    }

    int query(int l, int r, int x, int lx, int rx) {
        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;

bool operator<(pair<i128, i128> a, pair<i128, i128> b) {
    return a.first * b.second < a.second * b.first;
}

segtreeY st;

int answer() {
    alive.insert(0);
    if (alive.empty()) {
        return st.t[1] % MOD;
    }
    auto it = alive.end();
    pair<i128, i128> ans = {0, 1};
    i128 prod = 1;
    do {
        it = prev(it);
        pair<i128, i128> now = {st.query(*it, n), prod};
        if (ans < now) {
            ans = now;
        }
        prod *= x[*it];
        now = {1e9, prod};
        if (now < ans) {
            break;
        }
    } while (it != alive.begin());
    int val = mul(ans.first % MOD, inv(ans.second % MOD));
    return mul(prodX, val);
}

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);
        }
    }
    st.init(y);
    return answer();
}

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


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

Compilation message (stderr)

horses.cpp: In function 'int mul(int, int)':
horses.cpp:15:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   15 |     return a * (long long) b % MOD;
      |            ~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'void segtreeY::init(std::vector<int>)':
horses.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while (sz < a.size()) sz <<= 1;
      |                ~~~^~~~~~~~~~
horses.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < a.size(); ++i) {
      |                         ~~^~~~~~~~~~
horses.cpp: In function 'int answer()':
horses.cpp:114:51: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  114 |     int val = mul(ans.first % MOD, inv(ans.second % MOD));
      |                                        ~~~~~~~~~~~^~~~~
horses.cpp:114:29: warning: conversion from '__int128' to 'int' may change value [-Wconversion]
  114 |     int val = mul(ans.first % MOD, inv(ans.second % MOD));
      |                   ~~~~~~~~~~^~~~~

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