oj.uz

Submission #985349

# Submission time Handle Problem Language Result Execution time Memory
985349 2024-05-17T16:34:21 Z LucaIlie Horses (IOI15_horses) C++17
17 / 100
 161 ms 62652 KB 
#include <iostream>
#include <cmath>

using namespace std;

const int mod = 1e9 + 7;
#define nmax 500000

long long aint_rez[4 * nmax];

struct info{
    double val;
    int poz;
};

info aint[4 * nmax];
double lazy[4 * nmax];
int x[nmax], y[nmax];
double sp[nmax];
int n;


void init_aint_rez( int l, int r, int poz ) {
    if( l == r ) {
        aint_rez[poz] = x[l];
        return;
    }
    init_aint_rez( l, (l + r) / 2, 2 * poz );
    init_aint_rez( (l + r) / 2 + 1, r, 2 * poz + 1 );
    aint_rez[poz] = ( aint_rez[2 * poz] * aint_rez[2 * poz + 1] ) % mod;
}

void update_aint_rez( int l, int r, int lq, int val, int poz ) {
    if( lq < l || r < lq )
        return;
    if( l == r ) {
        aint_rez[l] = val;
        return;
    }
    update_aint_rez( l, (l + r) / 2, lq, val, 2 * poz );
    update_aint_rez( (l + r) / 2 + 1, r, lq, val, 2 * poz + 1 );
    aint_rez[poz] = ( aint_rez[2 * poz] * aint_rez[2 * poz + 1] ) % mod;
}

long long query_aint_rez( int l, int r, int lq, int rq, int poz ) {
    if( r < lq || rq < l )
        return 1;
    if( lq <= l && r <= rq )
        return aint_rez[poz];
    return ( query_aint_rez( l, (l + r) / 2, lq, rq, 2 * poz ) * query_aint_rez( (l + r) / 2 + 1, r, lq, rq, 2 * poz + 1 ) ) % mod;
}

void afiseaza( int l, int r, int poz ) {
    cout << l << " " << r << " " << poz << "      "<< aint[poz].poz << " " << aint[poz].val << " " << lazy[poz] << "\n";
    if( l == r )
        return;
    afiseaza( l, (l + r) / 2, 2 * poz );
    afiseaza( (l + r) / 2 + 1, r, 2 * poz + 1 );
}

void init_aint( int l, int r, int poz ) {
    if( l == r ) {
        aint[poz].val = sp[l] + log2( y[l] );
        aint[poz].poz = l;
        return;
    }
    init_aint( l, (l + r) / 2, poz * 2 );
    init_aint( (l + r) / 2 + 1, r, poz * 2 + 1 );
    if( aint[2 * poz].val < aint[2 * poz + 1].val ) {
        aint[poz].val = aint[2 * poz + 1].val;
        aint[poz].poz = aint[2 * poz + 1].poz;
    } else{
        aint[poz].val = aint[2 * poz].val;
        aint[poz].poz = aint[2 * poz].poz;
    }
}

void push_lazy( int l, int r, int poz ) {
    aint[poz].val += lazy[poz];
    if( l < r ) {
        lazy[2 * poz] += lazy[poz];
        lazy[2 * poz + 1] += lazy[poz];
    }
    lazy[poz] = 0;
}

void update_aint( int l, int r, int ql, int qr, double val, int poz ) {
    push_lazy( l, r, poz );
    if( r < ql || qr < l )
        return;
    if( ql <= l && r <= qr ) {
        lazy[poz] = val;
    } else {
        update_aint( l, (l + r) / 2, ql, qr, val, poz * 2 );
        update_aint( (l + r) / 2 + 1, r, ql, qr, val, poz * 2 + 1 );
        if( aint[2 * poz].val < aint[2 * poz + 1].val ) {
            aint[poz].val = aint[2 * poz + 1].val;
            aint[poz].poz = aint[2 * poz + 1].poz;
        } else{
            aint[poz].val = aint[2 * poz].val;
            aint[poz].poz = aint[2 * poz].poz;
        }
    }
    push_lazy( l, r ,poz );
}

int init( int N, int X[], int Y[] ) {
    n = N;
    int i;
    for( i = 1; i <= n; i++ )
        x[i] = X[i - 1];
    for( i = 1; i <= n; i++ )
        y[i] = Y[i - 1];
    for( i = 1; i <= n; i++ )
        sp[i] = sp[i - 1] + log2( x[i] );
    init_aint_rez( 1, n, 1 );
    init_aint( 1, n, 1 );
    //afiseaza( 1, n, 1 );
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

int updateX( int poz, int val ) {
    poz++;
    update_aint( 1, n, poz, n, log2(val ) - log2( x[poz] ), 1 );
    update_aint_rez( 1, n, poz, val, 1 );
    //afiseaza( 1, n, 1 );
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

int updateY( int poz, int val ) {
    poz++;
    //cout << "\n" << log2(val ) - log2( y[poz] ) << "\n";
    update_aint( 1, n, poz, poz, log2(val ) - log2( y[poz] ), 1 );
    //afiseaza( 1, n, 1 );
    //cout << aint[1].poz << "e ";
    y[poz] = val;
    return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:119:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  119 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:127:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:137:73: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |     return (query_aint_rez( 1, n, 1, aint[1].poz, 1) * y[aint[1].poz] ) % mod;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 4 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8656 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8648 KB Output is correct
18 Correct 1 ms 8536 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 1 ms 8644 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 46244 KB Output is correct
2 Incorrect 161 ms 62652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8544 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8544 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8544 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8640 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 2 ms 8636 KB Output is correct
21 Incorrect 1 ms 8540 KB Output isn't correct
22 Halted 0 ms 0 KB -