oj.uz

Submission #631582

# Submission time Handle Problem Language Result Execution time Memory
631582 2022-08-18T09:21:30 Z bachhoangxuan Secret (JOI14_secret) C++17
100 / 100
 472 ms 8304 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
#define MAX_VALUE 1000000000
#define maxn 1005
int dist[maxn][maxn],a[maxn],n;
/*
int Secret(int X,int Y){
    return (X + 2 * (Y / 2) < MAX_VALUE) ? (X + 2 * (Y / 2)) : MAX_VALUE;
}
*/
void update(int l,int r){
    if(l>r) return;
    if(l==r){
        dist[l][r]=a[r];
        return;
    }
    int mid=(l+r)>>1;
    dist[mid][mid]=a[mid];
    if(l<mid) dist[mid][mid-1]=a[mid-1];
    for(int i=mid+1;i<=r;i++) dist[mid][i]=Secret(dist[mid][i-1],a[i]);
    for(int i=mid-2;i>=l;i--) dist[mid][i]=Secret(a[i],dist[mid][i+1]);
    update(l,mid-1);update(mid+1,r);
}
int get(int l,int r,int tl,int tr){
    int mid=(l+r)>>1;
    if(mid>=tl && mid<=tr){
        if(mid==tl) return dist[mid][tr];
        else return Secret(dist[mid][tl],dist[mid][tr]);
    }
    if(mid<tl) return get(mid+1,r,tl,tr);
    else return get(l,mid-1,tl,tr);
}
void Init(int N, int A[]){
    n=N;
    for(int i=0;i<N;i++) a[i+1]=A[i];
    update(1,n);
}
int Query(int L, int R) {
    L++;R++;
    return get(1,n,L,R);
}
/*
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    Init(n,a);
    int q;cin >> q;
    while(q--){
        int l,r;cin >> l >> r;
        cout << Query(l,r) << '\n';
    }
}
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 4464 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 148 ms 4452 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 124 ms 4372 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 439 ms 8244 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 461 ms 8204 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 457 ms 8304 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 439 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 468 ms 8288 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 472 ms 8240 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 451 ms 8280 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1