oj.uz

Submission #1064931

# Submission time Handle Problem Language Result Execution time Memory
1064931 2024-08-18T19:36:31 Z hyakup Meetings (IOI18_meetings) C++17
19 / 100
 3449 ms 7760 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);
  if( q <= 50000 ){

    vector<ll> respL(n);
    for( int i = 0; i < q; i++ ){
      int l = L[i], r = R[i];
      resp[i] = inf*inf;

      stack<pair<int,ll>> pilha;
      pilha.push({ l - 1, inf });
      ll sum = 0;
      for( int j = l; j <= r; j++ ){
        while( pilha.top().second <= H[j] ){
          auto [id, v] = pilha.top(); pilha.pop();
          sum -= 1LL*v*abs(id - pilha.top().first);
        }
        sum += 1LL*H[j]*abs(j - pilha.top().first);
        pilha.push({ j, H[j] });
        respL[j] = sum;
      }

      while( !pilha.empty() ) pilha.pop();
      pilha.push({ r + 1, inf });
      sum = 0;
      for( int j = r; j >= l; j-- ){
        while( pilha.top().second <= H[j] ){
          auto [id, v] = pilha.top(); pilha.pop();
          sum -= 1LL*v*abs(id - pilha.top().first);
        }
        sum += 1LL*H[j]*abs(j - pilha.top().first);
        pilha.push({ j, H[j] });
        resp[i] = min( resp[i], sum + respL[j] - H[j] );
      }

    }
    return resp; 
  }
  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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 221 ms 2136 KB Output is correct
11 Correct 705 ms 2136 KB Output is correct
12 Correct 220 ms 2140 KB Output is correct
13 Correct 714 ms 2204 KB Output is correct
14 Correct 202 ms 2140 KB Output is correct
15 Correct 201 ms 2136 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 3449 ms 3260 KB Output is correct
3 Correct 71 ms 5916 KB Output is correct
4 Incorrect 54 ms 7760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 3449 ms 3260 KB Output is correct
3 Correct 71 ms 5916 KB Output is correct
4 Incorrect 54 ms 7760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 2 ms 1884 KB Output is correct
6 Correct 1 ms 1884 KB Output is correct
7 Correct 1 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 2 ms 1884 KB Output is correct
10 Correct 221 ms 2136 KB Output is correct
11 Correct 705 ms 2136 KB Output is correct
12 Correct 220 ms 2140 KB Output is correct
13 Correct 714 ms 2204 KB Output is correct
14 Correct 202 ms 2140 KB Output is correct
15 Correct 201 ms 2136 KB Output is correct
16 Correct 1 ms 1880 KB Output is correct
17 Correct 3449 ms 3260 KB Output is correct
18 Correct 71 ms 5916 KB Output is correct
19 Incorrect 54 ms 7760 KB Output isn't correct
20 Halted 0 ms 0 KB -