Submission #1239650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239650		walizamanee	Nile (IOI24_nile)	C++20	100 / 100	94 ms	12224 KiB

nile

#include<bits/stdc++.h>
#include "nile.h"
using namespace std;
using ll = long long;

vector<pair<int , int>> arr , e , arrtwo;
vector<pair<int , pair<int , int>>> w;
int n , q , par[1000001] , choto[100001] , koita[100001] , jor[2][100001] , uno , dos; // ek = min odd
long long sum , one , two , uttor ;
int st[400001] , bam[100001] , dan[100001];

void update( int node , int l , int r , int idx ) {
   if( l == r ) st[node] = w[idx].second.first - w[idx].second.second;
   else{
      int m = ( l + r ) / 2;
      if( idx <= m ) update(node * 2 , l , m , idx );
      else update( (node * 2) + 1 , m + 1 , r , idx );
      st[node] = min( st[node * 2] , st[(node * 2) + 1] );
   }
}

void getans( int node , int l , int r , int shu , int she ) {
   if( l >= shu && r <= she ) uno = min( uno , st[node] );
   else{
      int m = (l + r ) / 2;
      if( shu <= m ) getans( node * 2 , l , m , shu , she );
      if( she >= m + 1 ) getans( (node * 2) + 1 , m + 1, r , shu , she );
     
   }
}

int findpar( int me ) {
    if( par[me] == me ) return me;
    else{
       par[me] = findpar( par[me] );
       return par[me];
    }
}

void uttorbanao( int me ) {
   uttor -= (ll)choto[me];
   choto[me] = 0;
   if( koita[me] % 2 == 1 ) {
   dos = jor[bam[me] % 2][me];
   uno = 1e9 + 2;
   getans( 1 , 0 , n - 1 , bam[me] , dan[me] );
   uno = min( uno , dos );
   choto[me] = uno;
   uttor += (ll)choto[me];
   }
}

void comb( int a , int b ) {
    int aa = findpar( a );
    int bb = findpar( b );
    if( koita[aa] < koita[bb] ) swap( aa , bb );
    uttor -= choto[aa];
    uttor -= choto[bb];
    choto[aa] = 0;
    par[bb] = aa;
    koita[aa] += koita[bb];
    jor[0][aa] = min( jor[0][aa] , jor[0][bb]);
    jor[1][aa] = min( jor[1][aa] , jor[1][bb] );
    bam[aa] = min( bam[aa] , bam[bb] );
    dan[aa] = max( dan[aa] , dan[bb] );
    uttorbanao( aa );
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  n = (int)W.size();
  q = (int)E.size();
  w.clear();
  e.clear();
  for( int z = 0; z < n; z++ ){
     w.push_back({W[z] , {A[z] , B[z]}});
  }
  for( int z = 0; z < q; z++ ){
     e.push_back({E[z] , z});
  }
  sort( e.begin() , e.end() );
  sort( w.begin() , w.end() );
  arr.clear();
  arrtwo.clear();
  for( int z = 1; z < n; z++ ) {
    arr.push_back({w[z].first - w[z - 1].first , (z - 1) }); // n - 1
  }  
  for( int z = 1; z < n - 1; z++ ) {
     arrtwo.push_back({w[z + 1].first - w[z - 1].first , z}); // size n - 2
  }                                
  sort( arr.begin() , arr.end() );
  sort( arrtwo.begin() , arrtwo.end() );
 
  uttor = 0;
  for( int z = 0; z < n; z++ ) {
     choto[z] = w[z].second.first - w[z].second.second; // min tar sathe koto jog kora hocche

     par[z] = z;
     koita[z] = 1;
     uttor += (ll)w[z].second.first;
     jor[z % 2][z] = choto[z];
     jor[1 - (z % 2)][z] = 1e9 + 2;
     bam[z] = z;
     dan[z] = z;
  }
  int here = 0;
  int heretwo = 0;

  vector<long long> ans(q);
  for( int z = 0; z <= 4 * n; z++ ) st[z] = 1e9 + 2;

  for( int z = 0; z < q; z++ ) {

     while( heretwo < (n - 2) && e[z].first >= arrtwo[heretwo].first ) {
         int lol = arrtwo[heretwo].second;
         int lmao = findpar( lol );
         update( 1 , 0 , n - 1 , lol );

         jor[lol % 2][lmao] = min( jor[lol % 2][lmao] , jor[lol % 2][lol] );
         jor[1 - (lol % 2)][lmao] = min( jor[1 - (lol % 2)][lmao] , jor[1 - (lol % 2)][lol] );
         uttorbanao(lmao);
         heretwo++;
     }

     while( here < n - 1 && e[z].first >= arr[here].first ) {
         comb( arr[here].second , arr[here].second + 1 );
         here++;
     }
     ans[e[z].second] = uttor;
  }

  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18