oj.uz

Submission #714068

# Submission time Handle Problem Language Result Execution time Memory
714068 2023-03-23T19:31:30 Z EthanKim8683 Secret (JOI14_secret) C++17
100 / 100
 456 ms 4584 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
const I N=1000;
#ifdef ETHANKIM8683
void Init(I,I[]);
I Query(I,I);
I Secret(I x,I y){
  return x+y;
}
I main(){
  I n,q;cin>>n>>q;
  I a_arr[n];
  for(I i=0;i<n;i++)cin>>a_arr[i];
  Init(n,a_arr);
  while(q--){
    I l,r;cin>>l>>r;
    printf("%i\n",Query(l-1,r-1));
  }
}
#else
#include"secret.h"
#endif
I*a_arr;
vector<I>vals[2*N];
I n;
void slv(I i=1,I l=0,I r=n-1){
  if(l>r)return;
  I m=l+(r-l)/2;
  vals[i].resize(r-l+1);
  if(m>=l)vals[i][m-l]=a_arr[m];
  if(m+1<=r)vals[i][m+1-l]=a_arr[m+1];
  for(I j=m;j-1>=l;j--)vals[i][j-1-l]=Secret(a_arr[j-1],vals[i][j-l]);
  for(I j=m+1;j+1<=r;j++)vals[i][j+1-l]=Secret(vals[i][j-l],a_arr[j+1]);
  slv(i<<1,l,m-1),slv(i<<1|1,m+1,r);
}
I qry(I l1,I r1,I i=1,I l2=0,I r2=n-1){
  I m=l2+(r2-l2)/2;
  if(r1<m)return qry(l1,r1,i<<1,l2,m-1);
  if(l1>m)return qry(l1,r1,i<<1|1,m+1,r2);
  return r1==m?vals[i][l1-l2]:Secret(vals[i][l1-l2],vals[i][r1-l2]);
}
void Init(I _n,I _a_arr[]){
  n=_n,a_arr=_a_arr,slv();
}
I Query(I l,I r){
  return qry(l,r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 2376 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 131 ms 2340 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 135 ms 2380 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 432 ms 4372 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 440 ms 4456 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 450 ms 4264 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 456 ms 4268 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 444 ms 4356 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 441 ms 4584 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 447 ms 4304 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1