oj.uz

Submission #294369

# Submission time Handle Problem Language Result Execution time Memory
294369 2020-09-08T20:18:43 Z fucking_do_it Secret (JOI14_secret) C++14
100 / 100
 533 ms 8440 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];
vector<pair<int,int> > ranges;

void build(int l,int r){

    ranges.push_back(make_pair(l,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++;
    for(auto o:ranges){
        int l = o.first,r = o.second;
        if(!(x >= l && r >= y && mid >=x && mid <= y))
            continue;
        if(y == mid || x == mid+1)
            return dp[x][y];
        else
            return Secret(dp[x][mid],dp[mid+1][y]);
    }
 }

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 4600 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 155 ms 4516 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 151 ms 4544 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 524 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 527 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 533 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 525 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 524 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 525 ms 8316 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 528 ms 8440 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1