Submission #239711

#	Time	Username	Problem	Language	Result	Execution time	Memory
239711		abacaba	Horses (IOI15_horses)	C++14	17 / 100	687 ms	42744 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 all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ld long double
#define pll 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 = 5e5 + 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(int a, int b) {
    a %= mod, b %= mod;
    return 1ll * a * b % mod;
}

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

inline int dv(int a, int 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;
    }
    inline int get(int l, int r) {
        return dv(get(r), get(l - 1));
    }
} fenw;

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

    ll prod = 1;
    while(non_zero_x.size() > 32)
        non_zero_x.erase(non_zero_x.begin());
    for(set <int>::reverse_iterator it = non_zero_x.rbegin(); it != non_zero_x.rend(); ++it) {
        now.pb(*it);
        prod *= x[*it];
        // if(prod > 1000000000LL)
        //     break;
    }

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

    prod = 1;
    pll ans(-1, 0);
    for(int j = 0; j < now.size(); ++j) {
        int cur_y = t.get(1, 1, n, now[j], n);
        prod *= x[now[j]];
        if(ans.f == -1 || cur_y * prod > ans.se)
            ans = {now[j], cur_y * prod};
        // cout << now[j] << ' ' << cur_y << ' ' << prod << endl;
    }
    // cout << ans.f << ' ' << ans.se << endl;
    if(now.empty())
        return t.get(1, 1, n, 1, n);
    return mt(ans.se, 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) {
    if(non_zero_x.find(pos + 1) != non_zero_x.end())
        non_zero_x.erase(pos + 1);

    fenw.inc(pos + 1, binpow(x[pos + 1], mod - 2));

    x[pos + 1] = val;

    if(val != 1)
        non_zero_x.insert(pos + 1);
    fenw.inc(pos + 1, x[pos + 1]);

    return calc_ans();
}

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

Compilation message (stderr)

horses.cpp: In member function 'void segment_tree::update(int, int, int, int, int)':
horses.cpp:78: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:91:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = tl + tr >> 1;
                   ~~~^~~~
horses.cpp: In function 'int mt(int, int)':
horses.cpp:98:24: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
     return 1ll * a * b % mod;
            ~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int binpow(int, int)':
horses.cpp:101:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 inline int binpow(int n, int k) {
                               ^
horses.cpp:66:5: note: shadowed declaration is here
 int n, x[N], y[N];
     ^
horses.cpp: In function 'int calc_ans()':
horses.cpp:153:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < now.size(); ++j) {
                    ~~^~~~~~~~~~~~
horses.cpp:25:12: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define se second
            ^
horses.cpp:163:19: note: in expansion of macro 'se'
     return mt(ans.se, fenw.get(now[0] - 1));
                   ^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:166:33: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:64:11: note: shadowed declaration is here
 const int N = 5e5 + 15;
           ^

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