oj.uz

Submission #984240

# Submission time Handle Problem Language Result Execution time Memory
984240 2024-05-16T11:58:11 Z LucaIlie Horses (IOI15_horses) C++17
34 / 100
 1500 ms 45652 KB 
#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

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

struct AIB1 {
    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 AIB2 {
    double aib[MAX_N + 1];


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

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

    double query( int i ) {
        double p = 0;
        while ( i > 0 ) {
            p += aib[i];
            i -= (i & -i);
        }
        return p;
    }
} 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];
set<pair<double, int>> s;


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

int answer() {
    calc();
    int i = s.rbegin()->second;
    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];

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

    return answer();
}

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

    s.erase( { cost.query( i ) + log( y[i] ), i } );
    cost.update( i, -log( x[i] ) );
    horses.update( i, inv( x[i] ) );

    x[i] = val;

    cost.update( i, log( x[i] ) );
    horses.update( i, x[i] );
    s.insert( { cost.query( i ) + log( y[i] ), i } );

    return answer();
}

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

    s.erase( { cost.query( i ) + log( y[i] ), i } );
    y[i] = val;
    s.insert( { cost.query( i ) + log( y[i] ), i } );

    return answer();
}

Compilation message

horses.cpp: In member function 'void AIB1::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 AIB1::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:65:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   65 |     p = (long long)p * p % MOD;
      |         ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp:67:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |         p = (long long)p * a % MOD;
      |             ~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int answer()':
horses.cpp:95:48: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   95 |     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 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 3 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 3 ms 9816 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9916 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 3 ms 10072 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9896 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 3 ms 9916 KB Output is correct
11 Correct 3 ms 9816 KB Output is correct
12 Correct 2 ms 9816 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 3 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 6 ms 9820 KB Output is correct
23 Correct 431 ms 10112 KB Output is correct
24 Correct 408 ms 10140 KB Output is correct
25 Correct 454 ms 10112 KB Output is correct
26 Correct 361 ms 10120 KB Output is correct
27 Correct 393 ms 10324 KB Output is correct
28 Correct 372 ms 10112 KB Output is correct
29 Correct 365 ms 10120 KB Output is correct
30 Correct 365 ms 10072 KB Output is correct
31 Correct 371 ms 10120 KB Output is correct
32 Correct 420 ms 10116 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1538 ms 45400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9928 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 3 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 3 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 8 ms 10060 KB Output is correct
23 Correct 406 ms 10124 KB Output is correct
24 Correct 448 ms 10120 KB Output is correct
25 Correct 406 ms 10128 KB Output is correct
26 Correct 395 ms 10120 KB Output is correct
27 Correct 419 ms 10116 KB Output is correct
28 Correct 372 ms 10324 KB Output is correct
29 Correct 362 ms 10116 KB Output is correct
30 Correct 368 ms 10324 KB Output is correct
31 Correct 370 ms 10072 KB Output is correct
32 Correct 398 ms 10324 KB Output is correct
33 Execution timed out 1564 ms 45652 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 10064 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9852 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 3 ms 9820 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 3 ms 9816 KB Output is correct
22 Correct 6 ms 10064 KB Output is correct
23 Correct 394 ms 10128 KB Output is correct
24 Correct 400 ms 10072 KB Output is correct
25 Correct 362 ms 10116 KB Output is correct
26 Correct 356 ms 10124 KB Output is correct
27 Correct 391 ms 10332 KB Output is correct
28 Correct 408 ms 10116 KB Output is correct
29 Correct 392 ms 10132 KB Output is correct
30 Correct 355 ms 10076 KB Output is correct
31 Correct 379 ms 10324 KB Output is correct
32 Correct 438 ms 10076 KB Output is correct
33 Execution timed out 1567 ms 45392 KB Time limit exceeded
34 Halted 0 ms 0 KB -