| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 479065 |
2021-10-09T20:40:15 Z |
lollipop |
Addk (eJOI21_addk) |
C++14 |
|
459 ms |
11332 KB |
#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 ;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
5 ms |
460 KB |
Output is correct |
| 4 |
Correct |
8 ms |
588 KB |
Output is correct |
| 5 |
Correct |
10 ms |
588 KB |
Output is correct |
| 6 |
Correct |
16 ms |
844 KB |
Output is correct |
| 7 |
Correct |
18 ms |
892 KB |
Output is correct |
| 8 |
Correct |
20 ms |
844 KB |
Output is correct |
| 9 |
Correct |
33 ms |
1308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
1884 KB |
Output is correct |
| 2 |
Correct |
103 ms |
2840 KB |
Output is correct |
| 3 |
Correct |
136 ms |
4484 KB |
Output is correct |
| 4 |
Correct |
235 ms |
8036 KB |
Output is correct |
| 5 |
Correct |
347 ms |
9024 KB |
Output is correct |
| 6 |
Correct |
373 ms |
8800 KB |
Output is correct |
| 7 |
Correct |
307 ms |
8868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
3764 KB |
Output is correct |
| 2 |
Correct |
358 ms |
9200 KB |
Output is correct |
| 3 |
Correct |
459 ms |
11332 KB |
Output is correct |
| 4 |
Correct |
394 ms |
10264 KB |
Output is correct |
