oj.uz

Submission #339844

# Submission time Handle Problem Language Result Execution time Memory
339844 2020-12-26T09:46:29 Z Thistle Secret (JOI14_secret) C++14
100 / 100
 535 ms 4616 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define vec vector
#define pb emplace_back
#define siz(a) (int)(a).size()

vec<ll>a;
class dsp{
  int n,rr;
  vec<vec<ll>>dat;
  vec<int>lgt;
  public:
  void init(int sz){
    n=sz;
    int cnt=1;//バケットサイズ
    while((1<<cnt)<n) cnt++;
    dat.assign(cnt,vec<ll>(n,0));
    rep(i,n) dat[0][i]=a[i];
    rng(k,1,cnt){
      for(int j=0;j+(1<<k)<n;j+=(1<<(k+1))){
        int t=j+(1<<k);
        dat[k][t-1]=a[t-1],dat[k][t]=a[t];
        for(int r=t-2;r>=j;r--){
          dat[k][r]=Secret(a[r],dat[k][r+1]);
        }
        for(int r=t+1;r<min(n,j+(1<<(k+1)));r++){
          dat[k][r]=Secret(dat[k][r-1],a[r]);
        }
      }
    }
    lgt.assign((1<<cnt),0);
    for(int i=2;i<(1<<cnt);i++) lgt[i]=lgt[i>>1]+1;
  }
  int query(int x,int y){
    if(x==y) return dat[0][x];
    int k=lgt[x^y];
    return Secret(dat[k][x],dat[k][y]);
  }
} dsp;
void Init(int N, int A[]) {
  rep(i,N) a.pb(A[i]);
  dsp.init(N);
}

int Query(int L, int R) {
  int k=dsp.query(L,R);
  return k;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 2544 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 2412 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 145 ms 2412 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 513 ms 4588 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 527 ms 4460 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 529 ms 4460 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
7 Correct 514 ms 4460 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 533 ms 4616 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 535 ms 4460 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 514 ms 4588 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1