oj.uz

Submission #56554

# Submission time Handle Problem Language Result Execution time Memory
56554 2018-07-11T16:49:40 Z ruhanhabib39 Secret (JOI14_secret) C++17
100 / 100
 681 ms 13688 KB 
#include "secret.h"
#include <algorithm>
using namespace std;

namespace {
   const int MAXN = 1000;
   int pref[4*MAXN + 10][MAXN + 10], suff[4*MAXN + 10][MAXN + 10];
   int *A, N;
   void build(int cn, int b, int e) {
      if(b == e) return;
      int m = (b + e) / 2;
      int L = cn << 1, R = L | 1;
      suff[L][m] = A[m];
      for(int i = m-1; i >= b; i--) {
         suff[L][i] = Secret(A[i], suff[L][i+1]);
      }
      pref[R][m+1] = A[m+1];
      for(int i = m+2; i <= e; i++) {
         pref[R][i] = Secret(pref[R][i-1], A[i]);
      }
      build(L, b, m); build(R, m+1, e);
   }
};

void Init(int N_, int *A_) {
   N = N_;
   A = A_;
   build(1, 0, N-1);
   pref[1][N-1] = Secret(suff[2][0], pref[3][N-1]);
}

int Query(int l, int r) {
   int cn = 1, b = 0, e = N-1;
   while(true) {
      if(l == b && r == e) {
         if(cn & 1) return pref[cn][r];
         else return suff[cn][l];
      }
      int m = (b + e) / 2;
      if(l <= m && m <= r) {
         if(r == m) return suff[cn<<1][l];
         else return Secret(suff[cn<<1][l], pref[cn<<1|1][r]);
      }
      if(r <= m) {
         cn = cn << 1;
         e = m;
      } else {
         cn = cn<<1 | 1;
         b = m+1;
      }
   }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 6904 KB Output is correct - number of calls to Secret by Init = 3579, maximum number of calls to Secret by Query = 1
2 Correct 172 ms 6988 KB Output is correct - number of calls to Secret by Init = 3587, maximum number of calls to Secret by Query = 1
3 Correct 172 ms 7188 KB Output is correct - number of calls to Secret by Init = 3596, maximum number of calls to Secret by Query = 1
4 Correct 613 ms 13056 KB Output is correct - number of calls to Secret by Init = 7970, maximum number of calls to Secret by Query = 1
5 Correct 681 ms 13140 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
6 Correct 605 ms 13308 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
7 Correct 614 ms 13452 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
8 Correct 639 ms 13588 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
9 Correct 604 ms 13684 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
10 Correct 651 ms 13688 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1