Submission #479065

#	Time	Username	Problem	Language	Result	Execution time	Memory
479065		lollipop	Addk (eJOI21_addk)	C++14	100 / 100	459 ms	11332 KiB

Main

#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define s second
#define f first
using namespace std ;
const int mod =  1000000007 ; 
map < int , int > ma ; 
const int N = 100005 ; 
const int N1 = ( - 1 ) *( INT_MAX ) ;
int node[ 4 * N ] ; 
int a[ N ] ;
int node1[ 4 * N ] ; 
int a1[ N ] ;
void build( int v , int vl , int vr ){
	if( vl == vr ){
		node[ v ] = a[ vl ] ;
		return ; 
	}
	int vm = ( vl + vr ) / 2 ;
	build( v + v  , vl , vm ) ; 
	build( v + v + 1 , vm + 1 , vr ) ; 
	node[ v ] = node[ v + v ] + node[ v + v + 1 ] ;
}
void build1( int v , int vl , int vr ){
	if( vl == vr ){
		node1[ v ] = a1[ vl ] ;
		return ; 
	}
	int vm = ( vl + vr ) / 2 ;
	build1( v + v  , vl , vm ) ; 
	build1( v + v + 1 , vm + 1 , vr ) ; 
	node1[ v ] = node1[ v + v ] + node1[ v + v + 1 ] ;
}
void update( int v , int vl , int vr , int pos , int x ){
	 if( vl == vr ){
	 	node[ v ] = x ; 
	 	a[ vl ] = x ; 
		 return ;  
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) update( v + v , vl , vm , pos , x ) ; 
	 else update( v + v + 1 , vm + 1 , vr , pos , x ) ; 
	 node[ v ] = node[ v + v ] + node[ v + v + 1 ] ; 
}
void update1( int v , int vl , int vr , int pos , int x ){
	 if( vl == vr ){
	 	node1[ v ] = x ; 
	 	a1[ vl ] = x ; 
		 return ;  
	 }
	 int vm = ( vl + vr ) / 2 ;
	 if( vm >= pos ) update1( v + v , vl , vm , pos , x ) ; 
	 else update1( v + v + 1 , vm + 1 , vr , pos , x ) ; 
	 node1[ v ] = node1[ v + v ] + node1[ v + v + 1 ] ; 
}
int get( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ){
		return node[ v ] ; 
	}
	int vm = ( vl + vr ) / 2 ;
	return get( v + v , vl , vm , l , min( r , vm ) ) + get( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
}
int get1( int v , int vl , int vr , int l , int r ){
	if( l > r ) return 0 ;
	if( vl == l && vr == r ){
		return node1[ v ] ; 
	}
	int vm = ( vl + vr ) / 2 ;
	return get1( v + v , vl , vm , l , min( r , vm ) ) + get1( v + v + 1 , vm + 1 , vr , max( l , vm + 1 ) , r ) ;
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
     int n , k ;
     cin >> n >> k ;
     int st = 1 ;
     for( int j = 1 ; j <= n ; j ++ ){
     	cin >> a[ j ] ; 
     	a1[ j ] =a[ j ] * st ; st ++ ; 
	 }
	 build( 1 , 1 , n ) ;
	 build1( 1 , 1 , n ) ; 
	 //cout << 100 << endl ; 
	int q ; 
	cin >> q ;
	while( q -- ){
		int qu ; 
		cin >> qu ; 
		if( qu == 1 ){
			vector < int > v ; 
			for( int j =0 ; j < k ; j ++ ){
				int x ; cin >> x ; v.pb( x ) ; 
			}
			int number = a[ v[ 0 ] ] ;
			for( int j = 1 ; j < k ; j ++ ){
				int x = v[ j ] ; 
				int z = v[ j - 1 ] ;
				int num = a[ x ] ;
				update( 1 , 1 , n , z , num ) ;
				update1( 1 , 1 , n , z , num * z ) ; 
			}
			update( 1 , 1 , n , v[ k - 1 ] , number ) ;
			update1( 1 , 1 , n , v[ k - 1 ] , number * v[ k - 1 ] ) ;
		}
		else{
			int l , r , m ;
			cin >> l >> r >> m ; 
			int ans = 0 ;
		    int num = r - l - m + 1 ; 
		    if( m > r - l + 1 ){
		    //	cout << m << " " << r - l + 1 << endl ;
		    	cout << 0 << endl ; continue ; 
			}
			int end1 = min( m - 1 , num ) + l - 1 ; 
			ans  += get1( 1 , 1 , n , l , end1 ) - ( l - 1 ) * get( 1 , 1 , n , l , end1 ) ; 
		    int begin1 = r - min( m - 1 , num ) + 1 ; 
			ans += ( r + 1 ) * get( 1 , 1 , n , begin1 , r ) - get1( 1 , 1 , n , begin1 , r ) ;
			int x = min( m - 1 , num ) + 1 ;
		    ans += get( 1 , 1 , n , end1 + 1 , begin1 - 1 ) * x ; 
			cout << ans << endl ; 
		}
		
	}
	
	
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8