oj.uz

Submission #620626

# Submission time Handle Problem Language Result Execution time Memory
620626 2022-08-03T07:39:41 Z radal Secret (JOI14_secret) C++17
100 / 100
 560 ms 12452 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){
        if (i != sz2) seg[v][i+sz1][0] = Secret(seg[u][sz1][0],seg[u|1][i][0]);
        else seg[v][i+sz1][0] = seg[v][i+sz1][1];
        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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 6492 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 133 ms 6552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 133 ms 6488 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 560 ms 12392 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 487 ms 12408 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 477 ms 12376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 492 ms 12452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 547 ms 12436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 485 ms 12436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 511 ms 12392 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1