oj.uz

Submission #659080

# Submission time Handle Problem Language Result Execution time Memory
659080 2022-11-16T12:17:36 Z Jeff12345121 Horses (IOI15_horses) C++14
34 / 100
 25 ms 13140 KB 
#include <bits/stdc++.h>
#include "horses.h"

#define REP(i,n) for(int i = 1; i <= (n); i++)
using namespace std;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#endif

const int nmax = 5005;
long long n,x[nmax],y[nmax],inf = (1LL << 60),MOD = 1000000007;
double logx[nmax],logy[nmax];

struct Node {
    long long horses_mod;
    double horses_log;

    long long max_value_mod;
    double max_value_log;
    bool operator == (const Node &other) const {
        return horses_mod == other.horses_mod &&
                horses_log == other.horses_log && 
                max_value_mod == other.max_value_mod &&
                max_value_log == other.max_value_log;
    }
};

Node create_node(int pos) {
    Node res;
    res.horses_mod = x[pos] % MOD;
    res.horses_log = logx[pos];
    res.max_value_mod = x[pos] * y[pos] % MOD;
    res.max_value_log = logx[pos] + logy[pos];
    return res;
}

Node NULL_NODE = {-inf,1.41,-inf,1.41};

Node merge_nodes(Node l, Node r) {
    if (l == NULL_NODE) {
        return r;
    }
    if (r == NULL_NODE) {
        return l;
    }

    Node res;
    res.horses_mod = l.horses_mod * r.horses_mod % MOD;
    res.horses_log = l.horses_log + r.horses_log;
    
    if (l.max_value_log > l.horses_log + r.max_value_log) {
        res.max_value_mod = l.max_value_mod;
        res.max_value_log = l.max_value_log;
    } else {
        res.max_value_mod = l.horses_mod * r.max_value_mod % MOD;
        res.max_value_log = l.horses_log + r.max_value_log;
    }
    return res;
}
struct SegTree {
    Node aint[nmax];
    void init(int node, int l, int r) {
        if (l == r) {
            aint[node] = create_node(l);
            return;
        }
        int mid = (l + r) / 2;
        init(node * 2 , l, mid);
        init(node * 2 + 1 , mid + 1, r);
        aint[node] = merge_nodes(aint[node * 2] , aint[node * 2 + 1]);   
    }
    SegTree () {}
    SegTree(int n) {
        init (1 , 0 , n - 1);
    }
    void update(int node, int l, int r, int pos) {
        if (l > pos || r < pos) {
            return;
        }

        if (pos == l && r == pos) {
            aint[node] = create_node(pos);
            return;
        }

        int mid = (l + r) / 2;
        update(node * 2 , l , mid, pos);
        update(node * 2 + 1 , mid + 1 , r, pos);
        aint[node] = merge_nodes(aint[node * 2] , aint[node * 2 + 1]);
    }

    Node query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return aint[node];
        }

        if (l > qr || r < ql) {
            return NULL_NODE;
        }

        int mid = (l + r) / 2;
        return merge_nodes(query(node * 2, l , mid , ql , qr),
                    query(node * 2 + 1, mid + 1, r, ql, qr));
    }
};

SegTree segTree;
int compute() {
    return segTree.query(1 , 0 , n - 1, 0, n - 1).max_value_mod;
}
int init(int tn, int* tx,int* ty) {
    n = tn;
    for (int i = 0; i < n; i++) {
        x[i] = tx[i];
        logx[i] = log(x[i]);
        y[i] = ty[i];
        logy[i] = log(ty[i]);
    }

    segTree = SegTree(n);
    return compute();
}
int updateX(int pos, int val) {
    x[pos] = val;
    logx[pos] = log(x[pos]);
    segTree.update(1,0,n - 1, pos);
    return compute();
}

int updateY(int pos, int val) {
    y[pos] = val;
    logy[pos] = log(y[pos]);
    segTree.update(1,0,n - 1, pos);
    return compute();
}

#ifdef LOCAL
int tx[nmax],ty[nmax];
int32_t main() {
    in >> n;
    for (int i = 0; i < n; i++) {
        in >> tx[i];
    }
    for (int i = 0; i < n; i++) {
        in >> ty[i];
    }

    out << init(n,tx,ty) << "\n";
    int m;
    in >> m;
    for (int i = 0; i < m; i++) {
        int type,pos,val;
        in >> type >> pos >> val;
        if (type == 0) {
            out << updateX(pos, val);
        }
        if (type == 1) {
            out << updateY(pos,val);
        }
    }
}
#endif

Compilation message

horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:75:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   75 |     SegTree(int n) {
      |             ~~~~^
horses.cpp:13:11: note: shadowed declaration is here
   13 | long long n,x[nmax],y[nmax],inf = (1LL << 60),MOD = 1000000007;
      |           ^
horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:75:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   75 |     SegTree(int n) {
      |             ~~~~^
horses.cpp:13:11: note: shadowed declaration is here
   13 | long long n,x[nmax],y[nmax],inf = (1LL << 60),MOD = 1000000007;
      |           ^
horses.cpp: In constructor 'SegTree::SegTree(int)':
horses.cpp:75:17: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   75 |     SegTree(int n) {
      |             ~~~~^
horses.cpp:13:11: note: shadowed declaration is here
   13 | long long n,x[nmax],y[nmax],inf = (1LL << 60),MOD = 1000000007;
      |           ^
horses.cpp: In function 'int compute()':
horses.cpp:111:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |     return segTree.query(1 , 0 , n - 1, 0, n - 1).max_value_mod;
      |                                  ~~^~~
horses.cpp:111:46: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |     return segTree.query(1 , 0 , n - 1, 0, n - 1).max_value_mod;
      |                                            ~~^~~
horses.cpp:111:51: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |     return segTree.query(1 , 0 , n - 1, 0, n - 1).max_value_mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:122:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |     segTree = SegTree(n);
      |                       ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:128:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  128 |     segTree.update(1,0,n - 1, pos);
      |                        ~~^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:135:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |     segTree.update(1,0,n - 1, pos);
      |                        ~~^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 568 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 536 KB Output is correct
11 Correct 1 ms 564 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 568 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 708 KB Output is correct
26 Correct 1 ms 704 KB Output is correct
27 Correct 1 ms 580 KB Output is correct
28 Correct 1 ms 580 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 11392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 568 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 564 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 540 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 576 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Runtime error 25 ms 13140 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 564 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 568 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 572 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 568 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 708 KB Output is correct
26 Correct 1 ms 600 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 600 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 576 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Runtime error 15 ms 11384 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -