Submission #239772

#	Time	Username	Problem	Language	Result	Execution time	Memory
239772		abacaba	Horses (IOI15_horses)	C++14	37 / 100	1027 ms	52472 KiB

horses

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define p__int128 pair<long long, long long>

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}

inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}

template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 15;

int n, x[N], y[N];
set <int> non_zero_x;

struct segment_tree {
    int t[N << 2];
    segment_tree() {
        memset(t, 0, sizeof(t));
    }
    void update(int v, int tl, int tr, int pos, int val) {
        if(tl == tr)
            t[v] = val;
        else {
            int mid = tl + tr >> 1;
            if(pos <= mid)
                update(v << 1, tl, mid, pos, val);
            else
                update(v << 1 | 1, mid + 1, tr, pos, val);
            t[v] = max(t[v << 1], t[v << 1 | 1]);
        }
    }
    int get(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l || l > r)
            return 0;
        if(tl >= l && tr <= r)
            return t[v];
        int mid = tl + tr >> 1;
        return max(get(v << 1, tl, mid, l, r), get(v << 1 | 1, mid + 1, tr, l, r));
    }
} t;

inline int mt(__int128 a, __int128 b) {
    a %= mod, b %= mod;
    return (__int128)a * b % mod;
}

inline int binpow(__int128 n, __int128 k) {
    int res = 1;
    while(k) {
        if(k & 1)
            res = mt(res, n);
        k >>= 1;
        n = mt(n, n);
    }
    return res;
}

inline int dv(__int128 a, __int128 b) {
    return mt(a, binpow(b, mod - 2));
}

struct fenwick {
    int t[N];
    fenwick() {
        fill(t, t + N, 1);
    }
    inline void inc(int i, int val) {
        for(; i <= n; i = (i | (i + 1)))
            t[i] = mt(t[i], val);
    }
    inline int get(int i) {
        int res = 1;
        for(; i > 0; i = (i & (i + 1)) - 1)
            res = mt(res, t[i]);
        return res;
    }
} fenw;

inline int calc_ans() {
    vector <int> now = {};

    __int128 prod = 1;
    for(set <int>::reverse_iterator it = non_zero_x.rbegin(); it != non_zero_x.rend(); ++it) {
        prod *= x[*it];
        now.pb(*it);
        if(prod > 1e15)
            break;
    }

    reverse(now.begin(), now.end());

    if(now.empty())
        return t.get(1, 1, n, 1, n);
    prod = 1;
    __int128 ans = 1;
    for(int j = 0; j < now.size(); ++j) {
        prod *= x[now[j]];
        Max(ans, t.get(1, 1, n, now[j], n) * prod);
    }
    return mt(ans, fenw.get(now[0] - 1));
}

int init(int N, int X[], int Y[]) {
    n = N;
    for(int i = 0; i < n; ++i) {
        x[i + 1] = X[i], y[i + 1] = Y[i];
        if(x[i + 1] != 1)
            non_zero_x.insert(i + 1);

        t.update(1, 1, n, i + 1, y[i + 1]);
        fenw.inc(i + 1, x[i + 1]);
    }
    return calc_ans();
}

int updateX(int pos, int val) {
    ++pos;
    fenw.inc(pos, binpow(x[pos], mod - 2));

    x[pos] = val;

    if(val == 1 && non_zero_x.count(pos))
        non_zero_x.erase(pos);

    fenw.inc(pos, x[pos]);

    return calc_ans();
}

int updateY(int pos, int val) {
    y[++pos] = val;
    t.update(1, 1, n, pos, y[pos]);
    return calc_ans();
}

Compilation message (stderr)

horses.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
horses.cpp:77:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = tl + tr >> 1;
                       ~~~^~~~
horses.cpp: In member function 'int segment_tree::get(int, int, int, int, int)':
horses.cpp:90:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = tl + tr >> 1;
                   ~~~^~~~
horses.cpp: In function 'int mt(__int128, __int128)':
horses.cpp:97:28: warning: conversion to 'int' from '__int128' may alter its value [-Wconversion]
     return (__int128)a * b % mod;
            ~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int binpow(__int128, __int128)':
horses.cpp:100:41: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 inline int binpow(__int128 n, __int128 k) {
                                         ^
horses.cpp:65:5: note: shadowed declaration is here
 int n, x[N], y[N];
     ^
horses.cpp: In function 'int calc_ans()':
horses.cpp:139:19: warning: conversion to 'double' from '__int128' may alter its value [-Wconversion]
         if(prod > 1e15)
                   ^~~~
horses.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < now.size(); ++j) {
                    ~~^~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:156:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:63:11: note: shadowed declaration is here
 const int N = 1e6 + 15;
           ^

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