Submission #1091996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091996		triplem5ds	Horses (IOI15_horses)	C++14	0 / 100	613 ms	48212 KiB

horses

#include "horses.h"
#include "bits/stdc++.h"
using namespace std;


const int MOD = 1e9 + 7;
const int N = 5e5 + 5;

struct segTreeNode
{
    int mulX;
    int maxY;
    segTreeNode(int _mulX = 0, int _maxY = 0) : mulX(_mulX), maxY(_maxY) {}
    friend segTreeNode operator + (segTreeNode a, segTreeNode b) {
        return segTreeNode(
            1ll * a.mulX * b.mulX % MOD,
            max(a.maxY, b.maxY)
        );
    }
};

int x[N], y[N], n;
segTreeNode tree[N << 2];
set<int> hotPoints;

void build(int node, int s, int e) {
    if (s == e) {
        tree[node] = segTreeNode(x[s], y[s]);
        return;
    }
    int md = (s + e) >> 1;
    build(node << 1, s, md);
    build(node << 1 | 1, md + 1, e);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

segTreeNode query(int node, int s, int e, int l, int r) {
    if (r < s || e < l)  return segTreeNode(1, 0);
    if (l <= s && e <= r)
        return tree[node];
    int md = (s + e) >> 1;
    return query(node << 1, s, md, l, r) + query(node << 1 | 1, md + 1, e, l, r);
}

void update(int node, int s, int e, int index) {
    if (s == e) {
        tree[node] = segTreeNode(x[s], y[s]);
        return;
    }
    int md = (s + e) >> 1;
    if (index <= md)
        update(node << 1, s, md, index);
    else
        update(node << 1 | 1, md + 1, e, index);
    tree[node] = tree[node << 1] + tree[node << 1 | 1];
}

int calcAnswer() {

    if (hotPoints.empty()) return tree[1].maxY;
    vector<array<int, 3>> vec; ///(x, y)
    int prv = n;

    ///Extract last 30 elements
    for (auto it = hotPoints.rbegin(); it != hotPoints.rend() && vec.size() < 30; it++) {
        vec.push_back({
            x[*it],
            query(1, 0, n - 1, *it, prv - 1).maxY,
            *it
            });
        prv = *it;
    }

    reverse(begin(vec), end(vec));  ///reorder to go from first to last

    ///I want to get the best Y
    int choosen = 0;
    long long cur = 1;
    for (int i = 1; i < vec.size(); i++) {
        /*
            I want to get the first j > i such that
            x[i + 1] * ... * x[j] * y[j] > y[i]
        */
        cur = cur * vec[i][0];
        if (cur > vec[choosen][1] || cur * vec[i][1] > vec[choosen][1]) { ///to avoid overflow
            choosen = i;
            cur = 1;
        }
    }

    int nxt = n;
    if (choosen + 1 != vec.size()) nxt = vec[choosen + 1][2];
    auto val = query(1, 0, n - 1, 0, nxt - 1);
    return 1ll * val.maxY * val.mulX % MOD;
}

int init(int N, int X[], int Y[]) {
    copy(X, X + N, x);
    copy(Y, Y + N, y);
    n = N;
    build(1, 0, N - 1);
    for (int i = 0; i < N; i++) {
        if (X[i] > 1) hotPoints.insert(i);
    }
    return calcAnswer();
}

int updateX(int pos, int val) {
    x[pos] = val;
    update(1, 0, n - 1, pos);
    return calcAnswer();
}

int updateY(int pos, int val) {
    y[pos] = val;
    update(1, 0, n - 1, pos);
    return calcAnswer();
}


// int main() {
//     int n = 3;
//     int x[] = { 2,1,3 };
//     int y[] = { 3,4,1 };
//     cout << init(n, x, y) << "\n";
//     cout << updateY(1, 2) << "\n";

// }

Compilation message (stderr)

horses.cpp: In function 'segTreeNode operator+(segTreeNode, segTreeNode)':
horses.cpp:16:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |             1ll * a.mulX * b.mulX % MOD,
      |             ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int calcAnswer()':
horses.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 1; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
horses.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     if (choosen + 1 != vec.size()) nxt = vec[choosen + 1][2];
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~
horses.cpp:94:38: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   94 |     return 1ll * val.maxY * val.mulX % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:97:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   97 | int init(int N, int X[], int Y[]) {
      |          ~~~~^
horses.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 5e5 + 5;
      |           ^

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