oj.uz

Submission #1101149

# Submission time Handle Problem Language Result Execution time Memory
1101149 2024-10-15T16:34:52 Z InvMOD Secret (JOI14_secret) C++14
100 / 100
 325 ms 8296 KB 
#include<bits/stdc++.h>
#include "secret.h"
 
using namespace std;
 
const int N = 1e3+1;
 
int mx_size, pref[N][N];
 
/* Can be call so we can't create this
int Secret(int x, int y){
    return min(x + ((y>>1)<<1), (int)1e9);
}
*/
 
void Dnc(int l, int r, int a[]){
    if(l == r){
        pref[l][l] = a[l];
        return;
    }
 
    int m = l+r>>1;
    pref[m][m] = a[m];
    pref[m+1][m+1] = a[m+1];
 
    for(int i = m-1; i >= l; i--){
        pref[i][m] = Secret(a[i], pref[i+1][m]);
    }
    for(int i = m+2; i <= r; i++){
        pref[m+1][i] = Secret(pref[m+1][i-1], a[i]);
    }
 
    Dnc(l, m, a);
    Dnc(m+1, r, a);
    return;
}
 
void Init(int n, int a[]){
    --n; mx_size = n;
    Dnc(0, n, a);
    return;
}
 
int get(int l, int r, int Ql, int Qr){
    if(l == r){
        return pref[l][r];
    }
    else{
        int m = l+r>>1;
        if(Ql <= m && Qr > m){
            return Secret(pref[Ql][m], pref[m+1][Qr]);
        }
        else{
            if(Qr <= m){
                return get(l, m, Ql, Qr);
            }
            else{
                return get(m+1, r, Ql, Qr);
            }
        }
    }
    return -1;
}
 
int Query(int l, int r){
    return get(0, mx_size, l, r);
}

Compilation message

secret.cpp: In function 'void Dnc(int, int, int*)':
secret.cpp:22:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     int m = l+r>>1;
      |             ~^~
secret.cpp: In function 'int get(int, int, int, int)':
secret.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = l+r>>1;
      |                 ~^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 6728 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 85 ms 6772 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 86 ms 6728 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 325 ms 8292 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 311 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 310 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 321 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 318 ms 8296 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 318 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 312 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1