oj.uz

Submission #735801

# Submission time Handle Problem Language Result Execution time Memory
735801 2023-05-04T16:49:33 Z Wael Secret (JOI14_secret) C++14
100 / 100
 441 ms 9432 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int long long
#define F first
#define S second
//#define endl '\n'
#define INT INT_MAX
int const M = 1e3 + 30 , N = 3e6 , lg = 25 , mod = 1e9 + 7;
int dx[] = {0 , 0 , -1 , 1 , 1 , 1 , -1 , -1};
int dy[] = {1 , -1 , 0 , 0 , 1 , -1 , 1 , -1};
int T , n , j , a[M] , Q , l , r , Size = 1024 , s[M] , ans[M][M] , cnt;
bool vis[M][M];

void Go(int x = 1 , int lx = 1 , int rx = Size) {

    if(lx == rx) return;
    int mid = (lx + rx) / 2;
    int a = mid , b = mid + 1;
    for(int i = b + 1 ; i <= rx ; ++i) {
        if(!vis[b][i]) ans[b][i] = Secret(ans[b][i - 1] , s[i]);
        vis[b][i] = 1;
    }
    for(int i = a - 1 ; i >= lx ; --i) {
        if(!vis[i][a]) ans[i][a] = Secret(s[i] , ans[i + 1][a]);
        vis[i][a] = 1;
    }

    Go(2 * x , lx , mid);
    Go(2 * x + 1 , mid + 1 , rx);

}

int Get(int l , int r , int x = 1 , int lx = 1 , int rx = Size) {

    int mid = (lx + rx) / 2;
    if((mid >= l && mid <= r)) {
        int res = 0;
        if(mid < r) res = Secret(ans[l][mid] , ans[mid + 1][r]);
        else res = ans[l][mid];
        return res;
    }
    if(l > mid) return Get(l , r , 2 * x + 1 , mid + 1 , rx);
    else return Get(l , r , 2 * x,  lx , mid);

}

void Init(int sz , int ar[]) {

    n = sz;
    for(int i = 1 ; i <= n ; ++i) s[i] = ar[i - 1] , ans[i][i] = s[i];
    Go();

}

int Query(int l , int r) {

    ++cnt;
    ++l , ++r;
    if(l == r) return s[l];
    return Get(l , r);

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 7472 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
2 Correct 129 ms 7480 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
3 Correct 133 ms 7668 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
4 Correct 438 ms 9328 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
5 Correct 441 ms 9368 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
6 Correct 436 ms 9412 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
7 Correct 435 ms 9408 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
8 Correct 432 ms 9396 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
9 Correct 435 ms 9412 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1
10 Correct 430 ms 9432 KB Output is correct - number of calls to Secret by Init = 7190, maximum number of calls to Secret by Query = 1