oj.uz

답안 #553283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553283 2022-04-25T10:50:52 Z cadmiumsky 비밀 (JOI14_secret) C++14
100 / 100
 469 ms 4384 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e3 + 5;

vector<int> v;

namespace RMQ {
  int atr[nmax];
  int rmq[12][nmax];
  void color(int l, int r, int bit = 1) {
    //cerr << l << ' ' << r << ' ' << bit << '\n';
    if(l + 1 >= r) {
      while(l <= r)
        atr[l] = bit, l++;
      return;
    }
    int mid = l + r >> 1;
    atr[mid] = -bit;
    atr[mid + 1] = bit;
    color(l, mid - 1, bit + 1);
    color(mid + 2, r, bit + 1);
    rmq[bit][mid] = v[mid];
    rmq[bit][mid + 1] = v[mid + 1];
    for(int i = mid - 1; i >= l; i--)
      rmq[bit][i] = Secret(v[i], rmq[bit][i + 1]);
    for(int i = mid + 2; i <= r; i++)
      rmq[bit][i] = Secret(rmq[bit][i - 1], v[i]);
    return;
  }
  namespace IRMQ {
    pair<int,int> irmq[12][nmax];
    int lg[nmax];
    void init(int n, int *vec) {
      lg[1] = 0;
      for(int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
      for(int i = 0; i < n; i++)
        irmq[0][i] = {abs(vec[i]), vec[i] / abs(vec[i]) * i};
      for(int bit = 1; bit < 12; bit++) {
        for(int i = 0; i + (1 << bit) <= n; i++)
          irmq[bit][i] = min(irmq[bit - 1][i], irmq[bit - 1][i + (1 << bit - 1)]);
      }
    }
    pair<int,int> query(int l, int r) {
      int st = lg[r - l + 1];
      return min(irmq[st][l], irmq[st][r - (1 << st) + 1]);
    } 
  }
  int query(int l, int r) {
    if(l == r) 
      return v[l];
    else if(l == r - 1)
      return Secret(v[l], v[r]);
    auto level = IRMQ::query(l, r);
    if(r == -level.second)
      return rmq[level.first][l];
    if(l == level.second)
      return rmq[level.first][r];
    
    return Secret(rmq[level.first][l], rmq[level.first][r]);
  }
}


void Init(int N, int A[]) {
  v.resize(N);
  for(int i = 0; i < N; i++)
    v[i] = A[i];
  RMQ::color(0, N - 1);
  RMQ::IRMQ::init(N, RMQ::atr);
}

int Query(int L, int R) {
  return RMQ::query(L, R);
}

Compilation message

secret.cpp: In function 'void RMQ::color(int, int, int)':
secret.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
secret.cpp: In function 'void RMQ::IRMQ::init(int, int*)':
secret.cpp:42:76: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |           irmq[bit][i] = min(irmq[bit - 1][i], irmq[bit - 1][i + (1 << bit - 1)]);
      |                                                                        ~~~~^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 2428 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 121 ms 2444 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 142 ms 2380 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 446 ms 4384 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 461 ms 4300 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 425 ms 4360 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 456 ms 4336 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 469 ms 4316 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 436 ms 4304 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 453 ms 4328 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1