oj.uz

Submission #597738

# Submission time Handle Problem Language Result Execution time Memory
597738 2022-07-16T18:46:58 Z PiejanVDC Horses (IOI15_horses) C++17
100 / 100
 762 ms 119756 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

vector<long long>x,y;

long long mod = (long long)1000000007;

int last;
int ans;

int l,r;

vector<long long>mul(8*500000), correct_mul(8*500000), best(8*500000);

void build(int i, int j, int p) {
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    build(i, mid, 2*p);
    build(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

long long get_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return mul[p];
    int mid = (i+j)/2;
    return min(get_mul(i, mid, 2*p) * get_mul(mid+1, j, 2*p+1), (long long)1e9+5);
}

long long get_correct_mul(int i, int j, int p) {
    if(i > r || j < l)
        return 1;
    if(i >= l && j <= r)
        return correct_mul[p];
    int mid = (i+j)/2;
    return (get_correct_mul(i, mid, 2*p) * get_correct_mul(mid+1, j, 2*p+1))%mod;
}

void update(int i, int j, int p) {
    if(i > l || j < l)
        return;
    if(i == j) {
        mul[p] = correct_mul[p] = x[i];
        return;
    }
    int mid = (i+j)/2;
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
    mul[p] = mul[2*p] * mul[2*p+1];
    mul[p] = min(mul[p], (long long)1e9+5);
    correct_mul[p] = correct_mul[2*p] * correct_mul[2*p+1];
    correct_mul[p] %= mod;
}

void buld(int i, int j, int p) {
    int n = x.size();
    if(i == j) {
        best[p] = i;
        return;
    }
    int mid = (i+j)/2;
    buld(i, mid, 2*p);
    buld(mid+1, j, 2*p+1);
    l = best[2*p]+1, r = best[2*p+1];
    if(y[best[2*p]] >= get_mul(0, n-1, 1) * y[best[2*p+1]])
        best[p] = best[2*p];
    else
        best[p] = best[2*p+1];
}

void updQ(int i, int j, int p) {
    int n = x.size();
    if(i > r || j < l)
        return;
    if(i == j)
        return;
    int mid = (i+j)/2;
    updQ(i, mid, 2*p);
    updQ(mid+1, j, 2*p+1);
    l = best[2*p]+1, r = best[2*p+1];
    if(y[best[2*p]] >= get_mul(0, n-1, 1) * y[best[2*p+1]])
        best[p] = best[2*p];
    else
        best[p] = best[2*p+1];
}

int calc(int i) {
    int n = x.size();
    l = 0, r = i;
    long long c = get_correct_mul(0, n-1, 1);
    c *= y[i];
    c %= mod;
    return c;
}

int init(int n, int X[], int Y[]) {
    for(int i = 0 ; i < n ; i++)
        x.push_back(X[i]), y.push_back(Y[i]);
    build(0, n-1, 1);
    buld(0, n-1, 1);
    return calc(best[1]);
}

int updateX(int p, int val) {
    int n = (int)x.size();
    x[p] = val;
    l = p, r = p;
    update(0, n-1, 1);
    updQ(0, n-1, 1);
    return calc(best[1]);
}

int updateY(int p, int val) {
    int n = (int)x.size();
    y[p] = val;
    l = p, r = p;
    update(0, n-1, 1);
    updQ(0, n-1, 1);
    return calc(best[1]);
}

Compilation message

horses.cpp: In function 'void buld(int, int, int)':
horses.cpp:65:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   65 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:73:18: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |     l = best[2*p]+1, r = best[2*p+1];
horses.cpp:73:36: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |     l = best[2*p]+1, r = best[2*p+1];
      |                                    ^
horses.cpp: In function 'void updQ(int, int, int)':
horses.cpp:81:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:89:18: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |     l = best[2*p]+1, r = best[2*p+1];
horses.cpp:89:36: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   89 |     l = best[2*p]+1, r = best[2*p+1];
      |                                    ^
horses.cpp: In function 'int calc(int)':
horses.cpp:97:19: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   97 |     int n = x.size();
      |             ~~~~~~^~
horses.cpp:102:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  102 |     return c;
      |            ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:110:24: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  110 |     return calc(best[1]);
      |                        ^
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:119:24: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  119 |     return calc(best[1]);
      |                        ^
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:128:24: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  128 |     return calc(best[1]);
      |                        ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 94120 KB Output is correct
2 Correct 34 ms 94172 KB Output is correct
3 Correct 35 ms 94160 KB Output is correct
4 Correct 34 ms 94172 KB Output is correct
5 Correct 35 ms 94212 KB Output is correct
6 Correct 34 ms 94156 KB Output is correct
7 Correct 38 ms 94224 KB Output is correct
8 Correct 35 ms 94232 KB Output is correct
9 Correct 37 ms 94236 KB Output is correct
10 Correct 39 ms 94164 KB Output is correct
11 Correct 35 ms 94156 KB Output is correct
12 Correct 34 ms 94200 KB Output is correct
13 Correct 34 ms 94136 KB Output is correct
14 Correct 35 ms 94180 KB Output is correct
15 Correct 36 ms 94144 KB Output is correct
16 Correct 34 ms 94168 KB Output is correct
17 Correct 37 ms 94168 KB Output is correct
18 Correct 36 ms 94236 KB Output is correct
19 Correct 34 ms 94232 KB Output is correct
20 Correct 34 ms 94240 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 94176 KB Output is correct
2 Correct 42 ms 94200 KB Output is correct
3 Correct 37 ms 94200 KB Output is correct
4 Correct 35 ms 94228 KB Output is correct
5 Correct 38 ms 94156 KB Output is correct
6 Correct 34 ms 94112 KB Output is correct
7 Correct 34 ms 94252 KB Output is correct
8 Correct 34 ms 94140 KB Output is correct
9 Correct 38 ms 94212 KB Output is correct
10 Correct 40 ms 94220 KB Output is correct
11 Correct 42 ms 94200 KB Output is correct
12 Correct 35 ms 94128 KB Output is correct
13 Correct 34 ms 94256 KB Output is correct
14 Correct 35 ms 94236 KB Output is correct
15 Correct 37 ms 94212 KB Output is correct
16 Correct 34 ms 94228 KB Output is correct
17 Correct 34 ms 94156 KB Output is correct
18 Correct 34 ms 94188 KB Output is correct
19 Correct 35 ms 94164 KB Output is correct
20 Correct 36 ms 94176 KB Output is correct
21 Correct 38 ms 94164 KB Output is correct
22 Correct 34 ms 94232 KB Output is correct
23 Correct 37 ms 94300 KB Output is correct
24 Correct 39 ms 94292 KB Output is correct
25 Correct 36 ms 94240 KB Output is correct
26 Correct 35 ms 94292 KB Output is correct
27 Correct 38 ms 94180 KB Output is correct
28 Correct 37 ms 94296 KB Output is correct
29 Correct 36 ms 94204 KB Output is correct
30 Correct 36 ms 94272 KB Output is correct
31 Correct 35 ms 94228 KB Output is correct
32 Correct 34 ms 94292 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 110984 KB Output is correct
2 Correct 509 ms 119752 KB Output is correct
3 Correct 565 ms 110980 KB Output is correct
4 Correct 556 ms 114728 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 94156 KB Output is correct
2 Correct 37 ms 94168 KB Output is correct
3 Correct 36 ms 94228 KB Output is correct
4 Correct 37 ms 94224 KB Output is correct
5 Correct 36 ms 94152 KB Output is correct
6 Correct 43 ms 94196 KB Output is correct
7 Correct 35 ms 94140 KB Output is correct
8 Correct 37 ms 94152 KB Output is correct
9 Correct 35 ms 94112 KB Output is correct
10 Correct 35 ms 94156 KB Output is correct
11 Correct 35 ms 94232 KB Output is correct
12 Correct 35 ms 94152 KB Output is correct
13 Correct 42 ms 94156 KB Output is correct
14 Correct 36 ms 94192 KB Output is correct
15 Correct 35 ms 94292 KB Output is correct
16 Correct 35 ms 94172 KB Output is correct
17 Correct 35 ms 94168 KB Output is correct
18 Correct 37 ms 94228 KB Output is correct
19 Correct 36 ms 94132 KB Output is correct
20 Correct 36 ms 94164 KB Output is correct
21 Correct 35 ms 94232 KB Output is correct
22 Correct 35 ms 94152 KB Output is correct
23 Correct 37 ms 94232 KB Output is correct
24 Correct 37 ms 94208 KB Output is correct
25 Correct 43 ms 94192 KB Output is correct
26 Correct 40 ms 94200 KB Output is correct
27 Correct 43 ms 94224 KB Output is correct
28 Correct 37 ms 94232 KB Output is correct
29 Correct 36 ms 94156 KB Output is correct
30 Correct 35 ms 94212 KB Output is correct
31 Correct 35 ms 94228 KB Output is correct
32 Correct 36 ms 94268 KB Output is correct
33 Correct 228 ms 110152 KB Output is correct
34 Correct 203 ms 110120 KB Output is correct
35 Correct 187 ms 117140 KB Output is correct
36 Correct 175 ms 117236 KB Output is correct
37 Correct 204 ms 108372 KB Output is correct
38 Correct 168 ms 109204 KB Output is correct
39 Correct 180 ms 108276 KB Output is correct
40 Correct 174 ms 112112 KB Output is correct
41 Correct 179 ms 108332 KB Output is correct
42 Correct 180 ms 108412 KB Output is correct
43 Correct 171 ms 112552 KB Output is correct
44 Correct 144 ms 112572 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94168 KB Output is correct
2 Correct 37 ms 94144 KB Output is correct
3 Correct 38 ms 94164 KB Output is correct
4 Correct 44 ms 94120 KB Output is correct
5 Correct 40 ms 94212 KB Output is correct
6 Correct 44 ms 94160 KB Output is correct
7 Correct 40 ms 94208 KB Output is correct
8 Correct 35 ms 94216 KB Output is correct
9 Correct 35 ms 94148 KB Output is correct
10 Correct 35 ms 94228 KB Output is correct
11 Correct 34 ms 94184 KB Output is correct
12 Correct 38 ms 94172 KB Output is correct
13 Correct 34 ms 94188 KB Output is correct
14 Correct 37 ms 94232 KB Output is correct
15 Correct 38 ms 94136 KB Output is correct
16 Correct 45 ms 94224 KB Output is correct
17 Correct 35 ms 94108 KB Output is correct
18 Correct 35 ms 94164 KB Output is correct
19 Correct 34 ms 94156 KB Output is correct
20 Correct 35 ms 94224 KB Output is correct
21 Correct 36 ms 94220 KB Output is correct
22 Correct 36 ms 94160 KB Output is correct
23 Correct 40 ms 94280 KB Output is correct
24 Correct 40 ms 94244 KB Output is correct
25 Correct 37 ms 94284 KB Output is correct
26 Correct 37 ms 94268 KB Output is correct
27 Correct 38 ms 94280 KB Output is correct
28 Correct 36 ms 94148 KB Output is correct
29 Correct 38 ms 94252 KB Output is correct
30 Correct 37 ms 94228 KB Output is correct
31 Correct 38 ms 94232 KB Output is correct
32 Correct 44 ms 94256 KB Output is correct
33 Correct 433 ms 111032 KB Output is correct
34 Correct 518 ms 119756 KB Output is correct
35 Correct 602 ms 111028 KB Output is correct
36 Correct 530 ms 114692 KB Output is correct
37 Correct 210 ms 110120 KB Output is correct
38 Correct 229 ms 110128 KB Output is correct
39 Correct 195 ms 117104 KB Output is correct
40 Correct 186 ms 117000 KB Output is correct
41 Correct 202 ms 108336 KB Output is correct
42 Correct 163 ms 109332 KB Output is correct
43 Correct 172 ms 108200 KB Output is correct
44 Correct 175 ms 112108 KB Output is correct
45 Correct 170 ms 108352 KB Output is correct
46 Correct 172 ms 108368 KB Output is correct
47 Correct 172 ms 112484 KB Output is correct
48 Correct 141 ms 112452 KB Output is correct
49 Correct 754 ms 112244 KB Output is correct
50 Correct 741 ms 112168 KB Output is correct
51 Correct 479 ms 118984 KB Output is correct
52 Correct 339 ms 118568 KB Output is correct
53 Correct 762 ms 110500 KB Output is correct
54 Correct 460 ms 111052 KB Output is correct
55 Correct 578 ms 109416 KB Output is correct
56 Correct 452 ms 113940 KB Output is correct
57 Correct 520 ms 109952 KB Output is correct
58 Correct 609 ms 110428 KB Output is correct
59 Correct 141 ms 112552 KB Output is correct