oj.uz

Submission #620609

# Submission time Handle Problem Language Result Execution time Memory
620609 2022-08-03T07:35:05 Z radal Secret (JOI14_secret) C++17
6 / 100
 536 ms 12488 KB 
#include <bits/stdc++.h>
#include "secret.h"
#pragma GCC target("sse,sse2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e3+10,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
int a[N],n;
int seg[N*4][N][2];
void build(int l,int r,int v = 1){
    if (r-l == 1){
        seg[v][1][0] = seg[v][1][1] = a[l];
        return;
    }
    int u = (v << 1),m = (l+r) >> 1;
    build(l,m,u);
    build(m,r,u|1);
    if (v == 1) return;
    int sz1 = m-l,sz2 = r-m;
    rep(i,1,sz1+1){
        seg[v][i][0] = seg[u][i][0];
        seg[v][i+sz2][1] = Secret(seg[u][i][1],seg[u|1][sz2][0]);
    }
    rep(i,1,sz2+1){
        seg[v][i+sz1][0] = Secret(seg[u][sz1][0],seg[u|1][i][0]);
        seg[v][i][1] = seg[u|1][i][1];
    }
}
int que(int l,int r,int s,int e,int v = 1){
    int u = (v << 1),m = (l+r) >> 1;
    if (e <= m) return que(l,m,s,e,u);
    if (s >= m) return que(m,r,s,e,u|1);
    return Secret(seg[u][m-s][1],seg[u|1][e-m][0]);
}
void Init(int nn,int A[]){
    n = nn;
    rep(i,0,n) a[i] = A[i];
    build(0,n);
}
int Query(int l, int r){
    r++;
    if (r == l+1){
        return a[l];
    }
    return que(0,n,l,r);
}

Subtask #1
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 6460 KB Output is correct - number of calls to Secret by Init = 4087, maximum number of calls to Secret by Query = 1
2 Correct 130 ms 6480 KB Output is correct - number of calls to Secret by Init = 4096, maximum number of calls to Secret by Query = 1
3 Correct 126 ms 6624 KB Output is correct - number of calls to Secret by Init = 4106, maximum number of calls to Secret by Query = 1
4 Partially correct 482 ms 12348 KB Output isn't correct - number of calls to Secret by Init = 8966, maximum number of calls to Secret by Query = 1
5 Partially correct 457 ms 12452 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
6 Partially correct 450 ms 12488 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
7 Partially correct 467 ms 12400 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
8 Partially correct 496 ms 12340 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
9 Partially correct 515 ms 12396 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
10 Partially correct 536 ms 12372 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1