oj.uz

Submission #406526

# Submission time Handle Problem Language Result Execution time Memory
406526 2021-05-17T17:23:00 Z bonopo Secret (JOI14_secret) C++14
6 / 100
 1004 ms 15500 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define el "\n"
#define f first
#define s second

typedef long long ll;
const ll MM=1e3+5, MOD=1e9+7;
int N, a[MM], pfx[12][MM], sfx[12][MM];
map<pair<int,int>, int> mem;

int Secret(int X, int Y);

int doSecret(int X, int Y) {
    if(mem.find({X, Y})!=mem.end()) return mem[{X, Y}];
    return mem[{X, Y}]=Secret(X, Y);
}

void build(int l, int r, int lvl) {
    int m=(l+r)/2;
    for(int i=l; i<=m; ++i) {
        int c=a[i];
        for(int j=i+1; j<=m; ++j) c=doSecret(c, a[j]);
        sfx[lvl][i]=c; }
    for(int i=m+1; i<=r; ++i) {
        if(i==m+1) pfx[lvl][i]=a[i];
        else pfx[lvl][i]=doSecret(pfx[lvl][i-1], a[i]); }
    if(l<r) build(l, m, lvl+1), build(m+1, r, lvl+1);
}

int qry(int l, int r, int ql, int qr, int lvl) {
    int m=(l+r)/2;

    if(ql<=m+1&&qr>=m) {
        int p=(qr==m+0?0:pfx[lvl][qr]);
        int s=(ql==m+1?0:sfx[lvl][ql]);

        if(qr==m+0) return s;
        if(ql==m+1) return p;
        return doSecret(s, p);
    }

    if(ql<=m&&qr<=m) return qry(l, m, ql, qr, lvl+1);
    else return qry(m+1, r, ql, qr, lvl+1);
}

void Init(int n, int A[]) {
    N=n;
    for(int i=0; i<N; ++i) a[i]=A[i];
    build(0, N-1, 0);
}

int Query(int L, int R) {
    return qry(0, N-1, L, R, 0);
}

Subtask #1
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 218 ms 5792 KB Output isn't correct - number of calls to Secret by Init = 43682, maximum number of calls to Secret by Query = 1
2 Partially correct 229 ms 5836 KB Output isn't correct - number of calls to Secret by Init = 43690, maximum number of calls to Secret by Query = 1
3 Partially correct 226 ms 5856 KB Output isn't correct - number of calls to Secret by Init = 43946, maximum number of calls to Secret by Query = 1
4 Partially correct 1004 ms 15388 KB Output isn't correct - number of calls to Secret by Init = 166628, maximum number of calls to Secret by Query = 1
5 Partially correct 878 ms 15500 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1
6 Partially correct 911 ms 15188 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1
7 Partially correct 876 ms 15476 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1
8 Partially correct 915 ms 15432 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1
9 Partially correct 873 ms 15408 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1
10 Partially correct 876 ms 15388 KB Output isn't correct - number of calls to Secret by Init = 166692, maximum number of calls to Secret by Query = 1