oj.uz

Submission #1092001

# Submission time Handle Problem Language Result Execution time Memory
1092001 2024-09-22T19:36:01 Z triplem5ds Horses (IOI15_horses) C++14
37 / 100
 1162 ms 48292 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() < 60; 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 6 ms 15964 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 6 ms 15920 KB Output is correct
4 Correct 7 ms 15964 KB Output is correct
5 Correct 6 ms 16052 KB Output is correct
6 Correct 6 ms 15964 KB Output is correct
7 Correct 6 ms 15964 KB Output is correct
8 Correct 6 ms 15960 KB Output is correct
9 Correct 9 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 5 ms 15960 KB Output is correct
13 Correct 5 ms 16016 KB Output is correct
14 Correct 5 ms 15964 KB Output is correct
15 Correct 6 ms 15964 KB Output is correct
16 Correct 6 ms 15992 KB Output is correct
17 Correct 5 ms 15964 KB Output is correct
18 Correct 5 ms 15924 KB Output is correct
19 Correct 5 ms 15964 KB Output is correct
20 Correct 6 ms 15964 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 6 ms 15964 KB Output is correct
4 Correct 6 ms 15960 KB Output is correct
5 Correct 6 ms 15980 KB Output is correct
6 Correct 9 ms 15964 KB Output is correct
7 Correct 7 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 15960 KB Output is correct
11 Correct 6 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 6 ms 15964 KB Output is correct
15 Correct 8 ms 15964 KB Output is correct
16 Correct 6 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 6 ms 15964 KB Output is correct
20 Correct 5 ms 15964 KB Output is correct
21 Correct 6 ms 16088 KB Output is correct
22 Correct 6 ms 15964 KB Output is correct
23 Correct 11 ms 16136 KB Output is correct
24 Correct 11 ms 16036 KB Output is correct
25 Correct 12 ms 15964 KB Output is correct
26 Correct 11 ms 16172 KB Output is correct
27 Incorrect 11 ms 15964 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 1084 ms 48168 KB Output is correct
2 Correct 1149 ms 48252 KB Output is correct
3 Correct 1124 ms 48292 KB Output is correct
4 Correct 1162 ms 48212 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15960 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 6 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 15964 KB Output is correct
10 Correct 5 ms 15872 KB Output is correct
11 Correct 6 ms 15964 KB Output is correct
12 Correct 5 ms 15960 KB Output is correct
13 Correct 5 ms 15964 KB Output is correct
14 Correct 5 ms 15964 KB Output is correct
15 Correct 6 ms 15988 KB Output is correct
16 Correct 6 ms 16008 KB Output is correct
17 Correct 5 ms 15964 KB Output is correct
18 Correct 6 ms 16008 KB Output is correct
19 Correct 6 ms 15964 KB Output is correct
20 Correct 5 ms 15964 KB Output is correct
21 Correct 6 ms 15964 KB Output is correct
22 Correct 6 ms 15964 KB Output is correct
23 Correct 11 ms 15964 KB Output is correct
24 Correct 10 ms 16128 KB Output is correct
25 Correct 13 ms 16216 KB Output is correct
26 Correct 11 ms 16180 KB Output is correct
27 Incorrect 10 ms 16128 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 16216 KB Output is correct
3 Correct 5 ms 15960 KB Output is correct
4 Correct 6 ms 16072 KB Output is correct
5 Correct 6 ms 15964 KB Output is correct
6 Correct 6 ms 16060 KB Output is correct
7 Correct 6 ms 15900 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 6 ms 15964 KB Output is correct
10 Correct 6 ms 15960 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 6 ms 16104 KB Output is correct
13 Correct 6 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 6 ms 15964 KB Output is correct
17 Correct 5 ms 15964 KB Output is correct
18 Correct 8 ms 15964 KB Output is correct
19 Correct 6 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 15964 KB Output is correct
23 Correct 12 ms 16148 KB Output is correct
24 Correct 11 ms 15964 KB Output is correct
25 Correct 12 ms 15964 KB Output is correct
26 Correct 11 ms 15996 KB Output is correct
27 Incorrect 10 ms 15964 KB Output isn't correct
28 Halted 0 ms 0 KB -