oj.uz

Submission #1092000

# Submission time Handle Problem Language Result Execution time Memory
1092000 2024-09-22T19:34:55 Z triplem5ds Horses (IOI15_horses) C++14
37 / 100
 712 ms 60752 KB 
#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;
        }
    }

    return 1ll * query(1, 0, n - 1, 0, vec[choosen][2]).mulX * vec[choosen][1] % 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) {
    if (x[pos] > 1)hotPoints.erase(pos);
    x[pos] = val;
    if (x[pos] > 1)hotPoints.insert(pos);
    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

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:91:80: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |     return 1ll * query(1, 0, n - 1, 0, vec[choosen][2]).mulX * vec[choosen][1] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:94:14: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   94 | 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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15964 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 5 ms 15896 KB Output is correct
10 Correct 6 ms 15964 KB Output is correct
11 Correct 9 ms 15964 KB Output is correct
12 Correct 5 ms 15964 KB Output is correct
13 Correct 5 ms 15964 KB Output is correct
14 Correct 5 ms 15964 KB Output is correct
15 Correct 5 ms 15964 KB Output is correct
16 Correct 5 ms 15960 KB Output is correct
17 Correct 5 ms 16100 KB Output is correct
18 Correct 5 ms 15960 KB Output is correct
19 Correct 5 ms 15964 KB Output is correct
20 Correct 5 ms 15964 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15964 KB Output is correct
6 Correct 6 ms 16132 KB Output is correct
7 Correct 6 ms 15964 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 6 ms 15964 KB Output is correct
10 Correct 6 ms 15964 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 6 ms 15964 KB Output is correct
13 Correct 5 ms 15964 KB Output is correct
14 Correct 6 ms 15964 KB Output is correct
15 Correct 5 ms 15964 KB Output is correct
16 Correct 5 ms 16004 KB Output is correct
17 Correct 7 ms 15940 KB Output is correct
18 Correct 6 ms 15964 KB Output is correct
19 Correct 5 ms 16076 KB Output is correct
20 Correct 5 ms 15960 KB Output is correct
21 Correct 6 ms 15964 KB Output is correct
22 Correct 6 ms 16100 KB Output is correct
23 Correct 8 ms 16160 KB Output is correct
24 Correct 8 ms 15960 KB Output is correct
25 Correct 12 ms 16128 KB Output is correct
26 Correct 9 ms 15964 KB Output is correct
27 Incorrect 8 ms 15956 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 48156 KB Output is correct
2 Correct 709 ms 60752 KB Output is correct
3 Correct 670 ms 52200 KB Output is correct
4 Correct 712 ms 56116 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 6 ms 15968 KB Output is correct
3 Correct 10 ms 15952 KB Output is correct
4 Correct 6 ms 15964 KB Output is correct
5 Correct 7 ms 15980 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 6 ms 16104 KB Output is correct
10 Correct 7 ms 15964 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 5 ms 15964 KB Output is correct
13 Correct 6 ms 15964 KB Output is correct
14 Correct 5 ms 15964 KB Output is correct
15 Correct 6 ms 15964 KB Output is correct
16 Correct 5 ms 15964 KB Output is correct
17 Correct 5 ms 15964 KB Output is correct
18 Correct 10 ms 16012 KB Output is correct
19 Correct 5 ms 15964 KB Output is correct
20 Correct 6 ms 15964 KB Output is correct
21 Correct 6 ms 15964 KB Output is correct
22 Correct 6 ms 15960 KB Output is correct
23 Correct 9 ms 16112 KB Output is correct
24 Correct 8 ms 16060 KB Output is correct
25 Correct 8 ms 16116 KB Output is correct
26 Correct 8 ms 16220 KB Output is correct
27 Incorrect 8 ms 15964 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 5 ms 15964 KB Output is correct
3 Correct 5 ms 15964 KB Output is correct
4 Correct 7 ms 15964 KB Output is correct
5 Correct 5 ms 15964 KB Output is correct
6 Correct 6 ms 15964 KB Output is correct
7 Correct 5 ms 16076 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 6 ms 15964 KB Output is correct
10 Correct 5 ms 15964 KB Output is correct
11 Correct 5 ms 16092 KB Output is correct
12 Correct 6 ms 15960 KB Output is correct
13 Correct 5 ms 16024 KB Output is correct
14 Correct 6 ms 15960 KB Output is correct
15 Correct 5 ms 15964 KB Output is correct
16 Correct 5 ms 15964 KB Output is correct
17 Correct 6 ms 15964 KB Output is correct
18 Correct 5 ms 15964 KB Output is correct
19 Correct 5 ms 15964 KB Output is correct
20 Correct 5 ms 16084 KB Output is correct
21 Correct 5 ms 15888 KB Output is correct
22 Correct 6 ms 15960 KB Output is correct
23 Correct 8 ms 15964 KB Output is correct
24 Correct 8 ms 15960 KB Output is correct
25 Correct 8 ms 15964 KB Output is correct
26 Correct 8 ms 15964 KB Output is correct
27 Incorrect 8 ms 15964 KB Output isn't correct
28 Halted 0 ms 0 KB -