oj.uz

Submission #659082

# Submission time Handle Problem Language Result Execution time Memory
659082 2022-11-16T12:18:59 Z Jeff12345121 Horses (IOI15_horses) C++14
100 / 100
 223 ms 127560 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 = 500005;
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[3 * 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 36 ms 94156 KB Output is correct
2 Correct 38 ms 94160 KB Output is correct
3 Correct 38 ms 94236 KB Output is correct
4 Correct 38 ms 94180 KB Output is correct
5 Correct 37 ms 94156 KB Output is correct
6 Correct 37 ms 94168 KB Output is correct
7 Correct 42 ms 94188 KB Output is correct
8 Correct 39 ms 94244 KB Output is correct
9 Correct 39 ms 94260 KB Output is correct
10 Correct 36 ms 94228 KB Output is correct
11 Correct 37 ms 94208 KB Output is correct
12 Correct 37 ms 94164 KB Output is correct
13 Correct 37 ms 94156 KB Output is correct
14 Correct 38 ms 94156 KB Output is correct
15 Correct 36 ms 94232 KB Output is correct
16 Correct 38 ms 94212 KB Output is correct
17 Correct 37 ms 94192 KB Output is correct
18 Correct 37 ms 94228 KB Output is correct
19 Correct 38 ms 94168 KB Output is correct
20 Correct 39 ms 94252 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94132 KB Output is correct
2 Correct 37 ms 94192 KB Output is correct
3 Correct 37 ms 94236 KB Output is correct
4 Correct 37 ms 94168 KB Output is correct
5 Correct 41 ms 94264 KB Output is correct
6 Correct 39 ms 94156 KB Output is correct
7 Correct 37 ms 94160 KB Output is correct
8 Correct 36 ms 94156 KB Output is correct
9 Correct 36 ms 94220 KB Output is correct
10 Correct 37 ms 94220 KB Output is correct
11 Correct 37 ms 94144 KB Output is correct
12 Correct 38 ms 94180 KB Output is correct
13 Correct 37 ms 94144 KB Output is correct
14 Correct 37 ms 94196 KB Output is correct
15 Correct 37 ms 94164 KB Output is correct
16 Correct 39 ms 94192 KB Output is correct
17 Correct 39 ms 94252 KB Output is correct
18 Correct 37 ms 94128 KB Output is correct
19 Correct 38 ms 94240 KB Output is correct
20 Correct 38 ms 94236 KB Output is correct
21 Correct 44 ms 94156 KB Output is correct
22 Correct 37 ms 94152 KB Output is correct
23 Correct 37 ms 94300 KB Output is correct
24 Correct 37 ms 94280 KB Output is correct
25 Correct 38 ms 94296 KB Output is correct
26 Correct 40 ms 94260 KB Output is correct
27 Correct 38 ms 94292 KB Output is correct
28 Correct 39 ms 94284 KB Output is correct
29 Correct 36 ms 94284 KB Output is correct
30 Correct 36 ms 94288 KB Output is correct
31 Correct 38 ms 94228 KB Output is correct
32 Correct 39 ms 94244 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 116376 KB Output is correct
2 Correct 223 ms 127304 KB Output is correct
3 Correct 172 ms 118532 KB Output is correct
4 Correct 196 ms 122316 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94236 KB Output is correct
2 Correct 38 ms 94156 KB Output is correct
3 Correct 38 ms 94200 KB Output is correct
4 Correct 37 ms 94196 KB Output is correct
5 Correct 39 ms 94160 KB Output is correct
6 Correct 38 ms 94200 KB Output is correct
7 Correct 37 ms 94184 KB Output is correct
8 Correct 37 ms 94152 KB Output is correct
9 Correct 38 ms 94212 KB Output is correct
10 Correct 38 ms 94164 KB Output is correct
11 Correct 42 ms 94236 KB Output is correct
12 Correct 38 ms 94248 KB Output is correct
13 Correct 37 ms 94156 KB Output is correct
14 Correct 37 ms 94128 KB Output is correct
15 Correct 38 ms 94124 KB Output is correct
16 Correct 38 ms 94176 KB Output is correct
17 Correct 37 ms 94204 KB Output is correct
18 Correct 38 ms 94284 KB Output is correct
19 Correct 38 ms 94228 KB Output is correct
20 Correct 37 ms 94244 KB Output is correct
21 Correct 38 ms 94192 KB Output is correct
22 Correct 39 ms 94156 KB Output is correct
23 Correct 38 ms 94288 KB Output is correct
24 Correct 39 ms 94260 KB Output is correct
25 Correct 38 ms 94188 KB Output is correct
26 Correct 38 ms 94204 KB Output is correct
27 Correct 40 ms 94284 KB Output is correct
28 Correct 41 ms 94284 KB Output is correct
29 Correct 41 ms 94284 KB Output is correct
30 Correct 38 ms 94188 KB Output is correct
31 Correct 38 ms 94196 KB Output is correct
32 Correct 38 ms 94220 KB Output is correct
33 Correct 86 ms 113840 KB Output is correct
34 Correct 88 ms 117772 KB Output is correct
35 Correct 114 ms 124684 KB Output is correct
36 Correct 119 ms 124596 KB Output is correct
37 Correct 78 ms 115896 KB Output is correct
38 Correct 83 ms 116796 KB Output is correct
39 Correct 71 ms 115836 KB Output is correct
40 Correct 95 ms 119824 KB Output is correct
41 Correct 72 ms 115888 KB Output is correct
42 Correct 75 ms 115904 KB Output is correct
43 Correct 90 ms 120052 KB Output is correct
44 Correct 89 ms 120060 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94156 KB Output is correct
2 Correct 39 ms 94160 KB Output is correct
3 Correct 39 ms 94156 KB Output is correct
4 Correct 37 ms 94224 KB Output is correct
5 Correct 38 ms 94232 KB Output is correct
6 Correct 38 ms 94176 KB Output is correct
7 Correct 38 ms 94156 KB Output is correct
8 Correct 41 ms 94260 KB Output is correct
9 Correct 38 ms 94180 KB Output is correct
10 Correct 38 ms 94228 KB Output is correct
11 Correct 37 ms 94148 KB Output is correct
12 Correct 38 ms 94164 KB Output is correct
13 Correct 37 ms 94148 KB Output is correct
14 Correct 38 ms 94252 KB Output is correct
15 Correct 38 ms 94148 KB Output is correct
16 Correct 38 ms 94172 KB Output is correct
17 Correct 37 ms 94212 KB Output is correct
18 Correct 37 ms 94232 KB Output is correct
19 Correct 37 ms 94212 KB Output is correct
20 Correct 38 ms 94156 KB Output is correct
21 Correct 40 ms 94156 KB Output is correct
22 Correct 38 ms 94228 KB Output is correct
23 Correct 38 ms 94292 KB Output is correct
24 Correct 38 ms 94248 KB Output is correct
25 Correct 38 ms 94196 KB Output is correct
26 Correct 38 ms 94268 KB Output is correct
27 Correct 38 ms 94240 KB Output is correct
28 Correct 38 ms 94284 KB Output is correct
29 Correct 38 ms 94284 KB Output is correct
30 Correct 40 ms 94316 KB Output is correct
31 Correct 37 ms 94208 KB Output is correct
32 Correct 38 ms 94240 KB Output is correct
33 Correct 130 ms 116420 KB Output is correct
34 Correct 218 ms 127560 KB Output is correct
35 Correct 175 ms 118476 KB Output is correct
36 Correct 189 ms 122372 KB Output is correct
37 Correct 90 ms 117804 KB Output is correct
38 Correct 90 ms 117740 KB Output is correct
39 Correct 113 ms 124708 KB Output is correct
40 Correct 120 ms 124696 KB Output is correct
41 Correct 82 ms 116020 KB Output is correct
42 Correct 81 ms 116800 KB Output is correct
43 Correct 71 ms 115772 KB Output is correct
44 Correct 93 ms 119756 KB Output is correct
45 Correct 73 ms 115912 KB Output is correct
46 Correct 78 ms 115956 KB Output is correct
47 Correct 91 ms 120124 KB Output is correct
48 Correct 89 ms 120088 KB Output is correct
49 Correct 182 ms 119748 KB Output is correct
50 Correct 182 ms 119820 KB Output is correct
51 Correct 177 ms 126564 KB Output is correct
52 Correct 178 ms 126152 KB Output is correct
53 Correct 167 ms 118180 KB Output is correct
54 Correct 142 ms 118704 KB Output is correct
55 Correct 128 ms 116880 KB Output is correct
56 Correct 162 ms 121612 KB Output is correct
57 Correct 124 ms 117624 KB Output is correct
58 Correct 129 ms 118316 KB Output is correct
59 Correct 92 ms 120064 KB Output is correct