oj.uz

Submission #294360

# Submission time Handle Problem Language Result Execution time Memory
294360 2020-09-08T20:02:24 Z fucking_do_it Secret (JOI14_secret) C++14
100 / 100
 516 ms 8696 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 1e3+9;
int n,a[inf],cnt;
int dp[inf][inf];

void build(int l,int r){

    if(l == r)
        return ;

    for(int i=mid-1;i>=l;i--)
        dp[i][mid] = Secret(a[i],dp[i+1][mid]);

    for(int i = mid+2;i<=r;i++)
        dp[mid+1][i] = Secret(dp[mid+1][i-1],a[i]);

    build(l,mid);
    build(mid+1,r);
}

void Init(int N, int A[]) {

    n = N;
    for(int i=1;i<=n;i++)
        a[i] = A[i-1],dp[i][i] = a[i];
    build(1,n);
    assert(cnt<=8000);

}

int Query(int x, int y) {
    x++,y++;
    if(x == y)return a[x];
    int l = 1,r = n;
    while(l != r){
        if(x <= mid && y>= mid+1)
            return Secret(dp[x][mid],dp[mid+1][y]);
       if(x>mid)
            l = mid+1;
       else
            r = mid;
    }
 }

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:46:2: warning: control reaches end of non-void function [-Wreturn-type]
   46 |  }
      |  ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4472 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 4728 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 4472 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 510 ms 8440 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 507 ms 8696 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 516 ms 8568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 516 ms 8352 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 8316 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 504 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 512 ms 8440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1