Submission #785340

#	Time	Username	Problem	Language	Result	Execution time	Memory
785340		lollipop	Horses (IOI15_horses)	C++17	100 / 100	455 ms	61176 KiB

horses

#include "horses.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 7e5 + 10 ;
const int MAXN = 1e9 + 10 ; 
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int nodex[ 4 * N ] ;
pair < int , int > nodey[ 4 * N ] ;
int x[ N ] , y[ N ] ;
void buildx( int v , int vl , int vr ){
	 if( vl == vr ){
	 	nodex[ v ] = x[ vl - 1 ] ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 buildx( v + v , vl , vm ) ;
	 buildx( v + v + 1 , vm + 1 , vr ) ;
	 nodex[ v ] = ( nodex[ v + v ] * nodex[ v + v + 1 ] ) % mod ; 
     return ;
}
void updatex( int v , int vl , int vr , int pos , int val ){
	 if( vl == vr ){
	 	nodex[ v ] = val ;
	 	x[ pos - 1 ] = val ; 
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ; 
	 if( vm >= pos )updatex( v + v , vl , vm , pos , val ) ;
	 else updatex( v + v + 1 , vm + 1 , vr , pos , val ) ;
	 nodex[ v ] = ( nodex[ v + v ] * nodex[ v + v + 1 ] ) % mod ; 
	 return ; 	 
}
int getx( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 1 ;
	if( vl == l && vr == r ){
		return nodex[ v ] ;
	}
	int vm = ( vl + vr ) / 2 ;
	int a = getx( v + v , vl , vm , l , min( r , vm ) ) ;
	int b = getx( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return ( a * b ) % mod ;
}

// for y 
void buildy( int v , int vl , int vr ){
	 if( vl == vr ){
	 	nodey[ v ] = { y[ vl - 1 ] , vl - 1 } ;
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ;
	 buildy( v + v , vl , vm ) ;
	 buildy( v + v + 1 , vm + 1 , vr ) ;
	 nodey[ v ] = max( nodey[ v + v ] , nodey[ v + v + 1 ] ) ; 
     return ;
}
void updatey( int v , int vl , int vr , int pos , int val ){
	 if( vl == vr ){
	 	nodey[ v ] = { val , vl - 1 } ;
	 	y[ vl - 1 ] = val ; 
	 	return ; 
	 }
	 int vm = ( vl + vr ) / 2 ; 
	 if( vm >= pos ) updatey( v + v , vl , vm , pos , val ) ;
	 else updatey( v + v + 1 , vm + 1 , vr , pos , val ) ;
	 nodey[ v ] = max( nodey[ v + v ] , nodey[ v + v + 1 ] ) ; 
	 return ; 	 
}
pair < int , int > gety( int v , int vl , int vr , int l , int r ){
	if( l > r ) return { 0 , 0 } ;
	if( vl == l && vr == r ){
		return nodey[ v ] ;
	}
	int vm = ( vl + vr ) / 2 ;
	pair < int , int > a = gety( v + v , vl , vm , l , min( r , vm ) ) ;
	pair < int , int > b = gety( v + v + 1 , vm + 1 , vr , max( vm + 1 , l ) , r ) ;
	return max( a , b ) ;
}
int n ;
set < int > se ; 
int pas(){
	int ans = 1 ; 
	int mx = 0 , lst = n ;
	int is_ok = n - 1 ; 
	for( auto yy : se ){
	   int X = -yy ;
	   pair < int , int > p = { 0 , 0 } ;
	   int l = X + 2 , r = lst ;
	   p = gety( 1 , 1 , n , l , r ) ;
	   if( p.f > mx ){
	   	  is_ok = p.s ; 
	   }
	   mx = max( mx , p.f ) ;
	   if( X == -1 ) break ; 
	   if( y[ X ] > mx ){
	   	  is_ok = X ; 
	   }
	   mx = max( mx , y[ X ] ) ;
	   mx = mx * x[ X ] ; 
	   if( mx > MAXN ) break ;
	   lst = X ; 	
	}
	ans = y[ is_ok ] * getx( 1 , 1 , n , 1 , is_ok + 1 ) ; 
	ans %= mod ;
	return ans ; 
	
}

signed init(signed N, signed X[], signed Y[]){
	 FOR( i , N ) x[ i ] = X[ i ] , y[ i ] = Y[ i ] ;
	 n = N ; 
	 se.insert( 1 ) ;
	 FOR( i , N ){
	 	if( x[ i ] != 1 ) se.insert( - i ) ;
	 }
	 buildx( 1 , 1 , n ) ;
	 buildy( 1 , 1 , n ) ;
	 return pas() ; 
}
signed updateX(signed pos, signed val){
	if( x[ pos ] != 1 ){
		se.erase( se.find( - pos ) ) ;
	}
	if( val != 1 ) se.insert( - pos ) ;
	updatex( 1 , 1 , n , pos + 1 , val ) ;
	return pas() ; 
}
signed updateY(signed pos, signed val){
	updatey( 1 , 1 , n , pos + 1 , val ) ;
	return pas() ;
}


//static char buffer[1024];
//static int currentChar = 0;
//static int charsNumber = 0;
//
//signed main() {
//  signed N;
//  cin >> N ; 
//
//  signed *X = (signed *)malloc(sizeof(int) * (unsigned int)N);
//  signed *Y = (signed *)malloc(sizeof(int) * (unsigned int)N);
//
//  for (int i = 0; i < N; i++) {
//    cin >> X[ i ] ; 
//  }
//
//  for (int i = 0; i < N; i++) {
//    cin >> Y[ i ] ; 
//  }
//
//  printf("%d\n", init(N, X, Y));
//
//  int M;
//  cin >> M ; 
//
//  for (int i = 0; i < M; i++) {
//    int type;
//     cin >> type ; 
//    int pos;
//     cin >> pos ; 
//    int val;
//     cin >> val ; 
//
//    if (type == 1) {
//      printf("%d\n", updateX(pos, val));
//    } else if (type == 2) {
//      printf("%d\n", updateY(pos, val));
//    }
//  }
//
//  return 0;
//}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:135:20: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  135 | signed init(signed N, signed X[], signed Y[]){
      |             ~~~~~~~^
horses.cpp:30:11: note: shadowed declaration is here
   30 | const int N = 7e5 + 10 ;
      |           ^
horses.cpp:144:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  144 |   return pas() ;
      |          ~~~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:152:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  152 |  return pas() ;
      |         ~~~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:156:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  156 |  return pas() ;
      |         ~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23