oj.uz

Submission #620592

# Submission time Handle Problem Language Result Execution time Memory
620592 2022-08-03T07:29:32 Z radal Secret (JOI14_secret) C++17
0 / 100
 485 ms 12448 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){
    if (l == s && r == e) return seg[v][r-l][0];
    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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 6568 KB Output is correct - number of calls to Secret by Init = 4087, maximum number of calls to Secret by Query = 1
2 Correct 134 ms 6476 KB Output is correct - number of calls to Secret by Init = 4096, maximum number of calls to Secret by Query = 1
3 Correct 131 ms 6600 KB Output is correct - number of calls to Secret by Init = 4106, maximum number of calls to Secret by Query = 1
4 Partially correct 467 ms 12448 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 478 ms 12376 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 461 ms 12396 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
7 Incorrect 448 ms 12448 KB Wrong Answer: Query(0, 999) - expected : 690201657, actual : 0.
8 Incorrect 481 ms 12404 KB Wrong Answer: Query(0, 999) - expected : 812884248, actual : 0.
9 Partially correct 470 ms 12348 KB Output isn't correct - number of calls to Secret by Init = 8976, maximum number of calls to Secret by Query = 1
10 Incorrect 485 ms 12448 KB Wrong Answer: Query(0, 999) - expected : 875372551, actual : 0.