oj.uz

Submission #556105

# Submission time Handle Problem Language Result Execution time Memory
556105 2022-05-02T11:05:49 Z urosk Secret (JOI14_secret) C++14
100 / 100
 465 ms 8372 KB 
#include "secret.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 1005
int a[maxn];
int c[maxn][maxn];
int n;
void init(int l,int r){
    if(l>=r) return;
    int mid = (l+r)/2;
    for(int i = mid+1;i<=r;i++) c[mid][i] = Secret(c[mid][i-1],a[i]);
    for(int i = mid-2;i>=l;i--) c[i][mid-1] = Secret(a[i],c[i+1][mid-1]);
    init(l,mid-1);
    init(mid+1,r);
}
void Init(int N, int A[]) {
    n = N;
    for(int i = 1;i<=n;i++) a[i] = A[i-1];
    for(int i = 1;i<=n;i++) c[i][i] = a[i];
    init(1,n);
}
int get(int tl,int tr,int l,int r){
    if(l==r) return c[l][r];
    int mid = (tl+tr)/2;
    if(mid-1>=l&&mid<=r) return Secret(c[l][mid-1],c[mid][r]);
    if(l==mid) return c[l][r];
    if(l>=mid) return get(mid+1,tr,l,r);
    return get(tl,mid-1,l,r);
}
int Query(int L, int R) {
    int ans = get(1,n,L+1,R+1);
    return ans;
}
/*
8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4376 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 128 ms 4472 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 136 ms 4428 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 461 ms 8240 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 465 ms 8260 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 456 ms 8252 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 453 ms 8268 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 457 ms 8260 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 458 ms 8372 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 441 ms 8228 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1