oj.uz

Submission #984339

# Submission time Handle Problem Language Result Execution time Memory
984339 2024-05-16T14:08:27 Z LucaIlie Horses (IOI15_horses) C++17
100 / 100
 1349 ms 61928 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5;
const int MOD = 1e9 + 7;

struct AIB {
    int aib[MAX_N + 1];

    void init() {
        for ( int i = 0; i <= MAX_N; i++ )
            aib[i] = 1;
    }

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] = (long long)aib[i] * x % MOD;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int p = 1;
        while ( i > 0 ) {
            p = (long long)p * aib[i] % MOD;
            i -= (i & -i);
        }
        return p;
    }
} horses;

struct info {
    long double maxx, pos;

    info operator + ( const info &x ) const {
        if ( x.maxx > maxx )
            return x;
        return *this;
    }
};

struct AINT {
    int lst, rst;
    info aint[4 * MAX_N];
    long double lazy[4 * MAX_N];

    void init( int l, int r ) {
        lst = l;
        rst = r;
    }

    void propag( int v, int l, int r ) {
        if ( aint[v].pos == 0 )
            aint[v].pos = l;

        aint[v].maxx += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru, long double x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] += x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
    }
    void update( int l, int r, long double x ) {
        update( 0, lst, rst, l, r, x );
    }

    info query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return { 0, 0 };

        if ( lq <= l && r <= rq )
            return aint[v];

        int mid = (l + r) / 2;
        info a = query( v * 2 + 1, l, mid, lq, rq );
        info b = query( v * 2 + 2, mid + 1, r, lq, rq );
        return a + b;
    }
    info query( int l, int r ) {
        return query( 0, lst, rst, l, r );
    }
} cost;

int lgPut( int a, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( a, n / 2 );
    p = (long long)p * p % MOD;
    if ( n % 2 == 1 )
        p = (long long)p * a % MOD;

    return p;
}

int inv( int x ) {
    return lgPut( x, MOD - 2 );
}

int n;
int x[MAX_N + 1], y[MAX_N + 1];


void calc() {
    horses.init();
    cost.init( 1, n );
    for ( int i = 1; i <= n; i++ ) {
        horses.update( i, x[i] );
        cost.update( i, n, log( x[i] ) );
        cost.update( i, i, log( y[i] ) );
    }
}

int answer() {
    int i = cost.query( 1, n ).pos;
    return (long long)horses.query( i ) * y[i] % MOD;
}

int init( int N, int X[], int Y[] ) {
    n = N;

    for ( int i = n - 1; i >= 0; i-- )
        x[i + 1] = X[i], y[i + 1] = Y[i];


    calc();
    printf( "\n\n" );
    return answer();
}

int updateX( int pos, int val ) {
    int i = pos + 1;

    cost.update( i, n, -log( x[i] ) );
    horses.update( i, inv( x[i] ) );

    x[i] = val;

    cost.update( i, n, log( x[i] ) );
    horses.update( i, x[i] );

    return answer();
}

int updateY( int pos, int val ) {
    int i = pos + 1;

    cost.update( i, i, -log( y[i] ) );
    y[i] = val;
    cost.update( i, i, log( y[i] ) );


    return answer();
}

Compilation message

horses.cpp: In member function 'void AIB::update(int, int)':
horses.cpp:19:44: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   19 |             aib[i] = (long long)aib[i] * x % MOD;
      |                      ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In member function 'int AIB::query(int)':
horses.cpp:27:39: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   27 |             p = (long long)p * aib[i] % MOD;
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int lgPut(int, int)':
horses.cpp:111:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  111 |     p = (long long)p * p % MOD;
      |         ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:113:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  113 |         p = (long long)p * a % MOD;
      |             ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int answer()':
horses.cpp:137:32: warning: conversion from 'long double' to 'int' may change value [-Wfloat-conversion]
  137 |     int i = cost.query( 1, n ).pos;
      |             ~~~~~~~~~~~~~~~~~~~^~~
horses.cpp:138:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |     return (long long)horses.query( i ) * y[i] % MOD;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7768 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7512 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7512 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 1 ms 7516 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 5 ms 7772 KB Output is correct
26 Correct 4 ms 7620 KB Output is correct
27 Correct 6 ms 7768 KB Output is correct
28 Correct 4 ms 7768 KB Output is correct
29 Correct 5 ms 7772 KB Output is correct
30 Correct 4 ms 7768 KB Output is correct
31 Correct 4 ms 7772 KB Output is correct
32 Correct 4 ms 7772 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 61484 KB Output is correct
2 Correct 1272 ms 61628 KB Output is correct
3 Correct 1263 ms 61740 KB Output is correct
4 Correct 1349 ms 61648 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7616 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct
13 Correct 2 ms 7772 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 3 ms 7620 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 4 ms 7768 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 4 ms 7596 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 6 ms 7772 KB Output is correct
28 Correct 6 ms 7808 KB Output is correct
29 Correct 4 ms 7772 KB Output is correct
30 Correct 4 ms 7772 KB Output is correct
31 Correct 4 ms 7772 KB Output is correct
32 Correct 4 ms 7788 KB Output is correct
33 Correct 1025 ms 60612 KB Output is correct
34 Correct 995 ms 60704 KB Output is correct
35 Correct 1010 ms 60884 KB Output is correct
36 Correct 974 ms 60768 KB Output is correct
37 Correct 975 ms 60616 KB Output is correct
38 Correct 983 ms 60892 KB Output is correct
39 Correct 947 ms 60780 KB Output is correct
40 Correct 954 ms 60740 KB Output is correct
41 Correct 990 ms 60932 KB Output is correct
42 Correct 957 ms 60776 KB Output is correct
43 Correct 949 ms 60496 KB Output is correct
44 Correct 971 ms 60708 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 1 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 1 ms 7516 KB Output is correct
10 Correct 1 ms 7516 KB Output is correct
11 Correct 1 ms 7516 KB Output is correct
12 Correct 2 ms 7592 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7512 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 4 ms 7772 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 4 ms 7800 KB Output is correct
28 Correct 4 ms 8024 KB Output is correct
29 Correct 4 ms 7772 KB Output is correct
30 Correct 4 ms 7772 KB Output is correct
31 Correct 4 ms 7772 KB Output is correct
32 Correct 4 ms 7772 KB Output is correct
33 Correct 1102 ms 61616 KB Output is correct
34 Correct 1259 ms 61728 KB Output is correct
35 Correct 1221 ms 61880 KB Output is correct
36 Correct 1322 ms 61616 KB Output is correct
37 Correct 1000 ms 60716 KB Output is correct
38 Correct 1006 ms 60600 KB Output is correct
39 Correct 971 ms 60748 KB Output is correct
40 Correct 974 ms 60584 KB Output is correct
41 Correct 948 ms 60752 KB Output is correct
42 Correct 949 ms 60720 KB Output is correct
43 Correct 934 ms 60716 KB Output is correct
44 Correct 974 ms 60584 KB Output is correct
45 Correct 935 ms 60756 KB Output is correct
46 Correct 934 ms 60748 KB Output is correct
47 Correct 947 ms 60516 KB Output is correct
48 Correct 942 ms 60648 KB Output is correct
49 Correct 1274 ms 61468 KB Output is correct
50 Correct 1210 ms 61720 KB Output is correct
51 Correct 1141 ms 61504 KB Output is correct
52 Correct 1205 ms 61644 KB Output is correct
53 Correct 1184 ms 61512 KB Output is correct
54 Correct 1151 ms 61604 KB Output is correct
55 Correct 1112 ms 60908 KB Output is correct
56 Correct 1195 ms 61508 KB Output is correct
57 Correct 1093 ms 61928 KB Output is correct
58 Correct 1114 ms 61684 KB Output is correct
59 Correct 939 ms 60756 KB Output is correct