oj.uz

Submission #1064929

# Submission time Handle Problem Language Result Execution time Memory
1064929 2024-08-18T19:34:36 Z hyakup Meetings (IOI18_meetings) C++17
0 / 100
 25 ms 3288 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const ll inf = 1e9 + 10;

const int maxn = 1e5 + 10;

vector<int> seg( 4*maxn );
void build( int pos, int ini, int fim, vector<int>& idL, vector<int>& idR ){
  if( ini == fim ){ seg[pos] = idR[ini] - idL[ini] - 1; return; }
  int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
  build( l, ini, mid, idL, idR );
  build( r, mid + 1, fim, idL, idR );
  seg[pos] = max( seg[l], seg[r] );
}

int query( int pos, int ini, int fim, int ki, int kf ){
  if( ki > fim || ini > kf ) return 0;
  if( ki <= ini && fim <= kf ) return seg[pos];
  int mid = ( ini + fim )/2;
  return max( query( 2*pos, ini, mid, ki, kf ), query( 2*pos + 1, mid + 1, fim, ki, kf ) );
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int n = H.size(), q = L.size();
  vector<ll> resp(q);
  vector<int> idL(n), idR(n);
  idL[0] = (( H[0] == 2 ) ? 0 : -1 );
  for( int i = 1; i < n; i++ ) idL[i] = (( H[i] == 2 ) ? i : idL[i - 1] );
  idR[n - 1] = (( H[n - 1] == 2 ) ? n - 1 : n );
  for( int i = n - 2; i >= 0; i-- ) idR[i] = (( H[i] == 2 ) ? i : idR[i + 1] );


  build( 1, 0, n - 1, idL, idR );

  for( int i = 0; i < q; i++ ){
    int l = L[i], r = R[i];
    resp[i] = 2*(r - l + 1) - max({ idR[l] - l, r - idL[r], query( 1, 0, n - 1, idR[l], idL[r] ) });
  }
  return resp;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 25 ms 3288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 25 ms 3288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -