oj.uz

Submission #620720

# Submission time Handle Problem Language Result Execution time Memory
620720 2022-08-03T08:32:37 Z mdn2002 Horses (IOI15_horses) C++14
0 / 100
 360 ms 121760 KB 
#include "horses.h"

#include<bits/stdc++.h>
using namespace std;
long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
pair < long long , long long > treemx [2000006];
set < int > vall;
void up ( int nod , int l , int r , int x , long long val )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        tree [nod] = val;
        return;
    }
    int mid = ( l + r ) / 2;
    up ( nod * 2 , l , mid , x , val );
    up ( nod * 2 + 1 , mid + 1 , r , x , val );
    tree [nod] = ( tree [ nod * 2 ] * tree [ nod * 2 + 1 ] ) % mod;
}
long long qr ( int nod , int l , int r , int x , int y )
{
    if ( y < l || r < x ) return 1;
    if ( x <= l && r <= y ) return tree [nod];
    int mid = ( l + r ) / 2;
    return ( qr ( nod * 2 , l , mid , x , y ) * qr ( nod * 2 + 1 , mid + 1 , r , x , y ) ) % mod;
}
void upmx ( int nod , int l , int r , int x , long long val )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        treemx [nod] = { val , l };
        return;
    }
    int mid = ( l + r ) / 2;
    upmx ( nod * 2 , l , mid , x , val );
    upmx ( nod * 2 + 1 , mid + 1 , r , x , val );
    treemx [nod] = max ( treemx [ nod * 2 ] , treemx [ nod * 2 + 1 ] );
}
pair < long long , long long > qrmx ( int nod , int l , int r , int x , int y )
{
    if ( y < l || r < x ) return { -1 , -1 };
    if ( x <= l && r <= y ) return treemx [nod];
    int mid = ( l + r ) / 2;
    return max ( qrmx ( nod * 2 , l , mid , x , y ) , qrmx ( nod * 2 + 1 , mid + 1 , r , x , y ) );
}
long long get ( )
{
    vector < int > ids , nig;

    ids . push_back ( n );

    if ( vall . size () )
    {
        set < int > :: iterator it = -- vall . end ();
        for ( it ; it != vall . begin () ; it -- )
        {
            ids . push_back ( * it );
            if ( ids . size () >= 50 ) break;
        }
    }
    if ( ids [ ids . size () - 1 ] != 0 ) ids . push_back ( 0 );

    reverse ( ids . begin () , ids . end () );

    for ( int i = 0 ; i < ids . size () ; i ++ )
    {
        if ( i )
        {
            int id = qrmx ( 1 , 0 , n , ids [ i - 1 ] + 1 , ids [i] - 1 ) . second;
            if ( id != -1 ) nig . push_back ( id );
        }
        if ( i != ids . size () - 1 ) nig . push_back ( ids [i] );
    }

    long long bst = 0 , mul = 1;
    for ( int i = 1 ; i < nig . size () ; i ++ )
    {
        int id = nig [i];
        mul *= x [id];
        if ( mul > y [bst] )
        {
            mul = 1;
            bst = id;
            continue;
        }
        long long almul = mul * y [id];
        if ( almul > y [bst] )
        {
            mul = 1;
            bst = id;
        }
    }

    long long bstt = 0 , mull = 1;
    for ( int i = 1 ; i < n ; i ++ )
    {
        int id = i;
        mul *= x [id];
        if ( mul > y [bst] )
        {
            mul = 1;
            bst = id;
            continue;
        }
        long long almul = mul * y [id];
        if ( almul > y [bst] )
        {
            mul = 1;
            bst = id;
        }
    }
    if ( bst != bstt )
    {
        for ( int i = 0 ; i < 1e9 ; i ++ ) 
        {
            bst ++;
            mul --;
        }
    }
    long long ans = qr ( 1 , 0 , n , 0 , bst );
    ans = ( ans * y [bst] ) % mod;
    return ans;
}

int init(int N, int X[], int Y[]) {

	n = N;
    for ( int i = 0 ; i < n ; i ++ )
    {
        x [i] = X [i];
        if ( x [i] > 1 ) vall . insert ( i );
        up ( 1 , 0 , n , i , x [i] );
    }
    for ( int i = 0 ; i < n ; i ++ )
    {
        y [i] = Y [i];
        upmx ( 1 , 0 , n , i , y [i] );
    }
    return get ();

}

int updateX(int pos, int val) {

	if ( x [pos] > 1 ) vall . erase ( vall . lower_bound ( pos ) );
    x [pos] = val;
    if ( x [pos] > 1 ) vall . insert ( pos );
    up ( 1 , 0 , n , pos , x [pos] );
	return get ();

}

int updateY(int pos, int val) {

	y [pos] = val;
    upmx ( 1 , 0 , n , pos , val );
	return get ();

}

Compilation message

horses.cpp: In function 'void up(int, int, int, int, long long int)':
horses.cpp:8:41: warning: declaration of 'x' shadows a global declaration [-Wshadow]
    8 | void up ( int nod , int l , int r , int x , long long val )
      |                                     ~~~~^
horses.cpp:5:35: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                   ^
horses.cpp: In function 'long long int qr(int, int, int, int, int)':
horses.cpp:21:54: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   21 | long long qr ( int nod , int l , int r , int x , int y )
      |                                                  ~~~~^
horses.cpp:5:48: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                                ^
horses.cpp:21:46: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   21 | long long qr ( int nod , int l , int r , int x , int y )
      |                                          ~~~~^
horses.cpp:5:35: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                   ^
horses.cpp: In function 'void upmx(int, int, int, int, long long int)':
horses.cpp:28:43: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   28 | void upmx ( int nod , int l , int r , int x , long long val )
      |                                       ~~~~^
horses.cpp:5:35: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                   ^
horses.cpp: In function 'std::pair<long long int, long long int> qrmx(int, int, int, int, int)':
horses.cpp:41:77: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   41 | pair < long long , long long > qrmx ( int nod , int l , int r , int x , int y )
      |                                                                         ~~~~^
horses.cpp:5:48: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                                ^
horses.cpp:41:69: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   41 | pair < long long , long long > qrmx ( int nod , int l , int r , int x , int y )
      |                                                                 ~~~~^
horses.cpp:5:35: note: shadowed declaration is here
    5 | long long n , m , mod = 1e9 + 7 , x [500005] , y [500005] , tree [2000006];
      |                                   ^
horses.cpp: In function 'long long int get()':
horses.cpp:52:23: warning: conversion from 'long long int' to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   52 |     ids . push_back ( n );
      |                       ^
horses.cpp:57:15: warning: statement has no effect [-Wunused-value]
   57 |         for ( it ; it != vall . begin () ; it -- )
      |               ^~
horses.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for ( int i = 0 ; i < ids . size () ; i ++ )
      |                       ~~^~~~~~~~~~~~~~~
horses.cpp:71:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |             int id = qrmx ( 1 , 0 , n , ids [ i - 1 ] + 1 , ids [i] - 1 ) . second;
      |                                     ^
horses.cpp:71:77: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |             int id = qrmx ( 1 , 0 , n , ids [ i - 1 ] + 1 , ids [i] - 1 ) . second;
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
horses.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if ( i != ids . size () - 1 ) nig . push_back ( ids [i] );
      |              ~~^~~~~~~~~~~~~~~~~~~~
horses.cpp:78:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for ( int i = 1 ; i < nig . size () ; i ++ )
      |                       ~~^~~~~~~~~~~~~~~
horses.cpp:122:34: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |     long long ans = qr ( 1 , 0 , n , 0 , bst );
      |                                  ^
horses.cpp:122:42: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  122 |     long long ans = qr ( 1 , 0 , n , 0 , bst );
      |                                          ^~~
horses.cpp:96:26: warning: unused variable 'mull' [-Wunused-variable]
   96 |     long long bstt = 0 , mull = 1;
      |                          ^~~~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:134:22: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |         up ( 1 , 0 , n , i , x [i] );
      |                      ^
horses.cpp:139:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |         upmx ( 1 , 0 , n , i , y [i] );
      |                        ^
horses.cpp:141:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  141 |     return get ();
      |            ~~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:150:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  150 |     up ( 1 , 0 , n , pos , x [pos] );
      |                  ^
horses.cpp:151:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  151 |  return get ();
      |         ~~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:158:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  158 |     upmx ( 1 , 0 , n , pos , val );
      |                    ^
horses.cpp:159:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  159 |  return get ();
      |         ~~~~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 2 ms 396 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 360 ms 121760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -