oj.uz

Submission #964569

# Submission time Handle Problem Language Result Execution time Memory
964569 2024-04-17T06:28:40 Z angella Secret (JOI14_secret) C++17
100 / 100
 394 ms 19144 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
#include "secret.h"

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;

int t, n, a[N];
vector<int> pr[N], sf[N];

void build(int ind, int lc, int rc) {
    if(lc>=rc-1) return;
    int mid = (lc+rc)/2;
    pr[ind].pb(a[mid]);
    for(int i=mid+1; i<rc; i++) pr[ind].pb(Secret(pr[ind][i-mid-1], a[i]));
    sf[ind].pb(a[mid-1]);
    for(int i=mid-2; i>=lc; i--) sf[ind].pb(Secret(a[i], sf[ind][mid-1-i-1]));
    build(2*ind, lc, mid); build(2*ind+1, mid, rc);
}

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

int qry(int l, int r, int ind, int lc, int rc) {
    int mid = (lc+rc)/2;
    int sz1=mid-l,sz2=r-mid;
    if(r == mid) {
        return sf[ind][sz1-1];
    }
    if(l == mid) {
        //fuck(pr[ind][sz2-1]);
        //cout<<lc<<' '<<rc<<' '<<sz1<<' '<<sz2<<endl;
        return pr[ind][sz2-1];
    }

    if(r<=mid) return qry(l, r, 2*ind, lc, mid);
    if(l>=mid) return qry(l, r, 2*ind+1, mid, rc);

    return Secret(sf[ind][sz1-1], pr[ind][sz2-1]);
}

int Query(int l, int r) {
    l++, r++;
    if(l == r) return a[l];
    int res = qry(l, r+1, 1, 1, n+1);
    // int x = a[l];
    // for(int i=l+1; i<=r; i++) x = Secret(x, a[i]);
    // if(res != x) {
    //     cout<<res<<' '<<x<<endl;
    // }
    //cout<<res<<endl;
    return res;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 19036 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 107 ms 19028 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 107 ms 19136 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 374 ms 19032 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 394 ms 19144 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 366 ms 19140 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 380 ms 19128 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 371 ms 19024 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 382 ms 19132 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 376 ms 19080 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1