oj.uz

Submission #406449

# Submission time Handle Problem Language Result Execution time Memory
406449 2021-05-17T15:29:15 Z bonopo Secret (JOI14_secret) C++14
0 / 100
 570 ms 4476 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#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[10][MM], sfx[10][MM];

int Secret(int X, int Y);

void build(int l, int r, int lvl) {
    int m=(l+r)/2;
    for(int i=m; i>=l; --i) {
        if(i==m) sfx[lvl][i]=a[i];
        else sfx[lvl][i]=Secret(a[i], sfx[lvl][i+1]); }
    for(int i=m+1; i<=r; ++i) {
        if(i==m+1) pfx[lvl][i]=a[i];
        else pfx[lvl][i]=Secret(a[i], pfx[lvl][i-1]); }
    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 Secret(p, s);
    }

    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 2372 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 542390582.
2 Incorrect 135 ms 2372 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 925507712.
3 Incorrect 146 ms 2368 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 562319420.
4 Incorrect 509 ms 4288 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 902447133.
5 Incorrect 518 ms 4344 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 19582988.
6 Incorrect 542 ms 4420 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7 Incorrect 513 ms 4428 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 99847218.
8 Incorrect 515 ms 4476 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 83895512.
9 Incorrect 514 ms 4468 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 819870670.
10 Incorrect 570 ms 4268 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 608725127.