oj.uz

Submission #964562

# Submission time Handle Problem Language Result Execution time Memory
964562 2024-04-17T06:09:49 Z angella Secret (JOI14_secret) C++17
0 / 100
 383 ms 19388 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(a[i], pr[ind][i-mid-1]));
    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) 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);
    //cout<<res<<endl;
    return res;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 19136 KB Wrong Answer: Query(113, 206) - expected : 536899947, actual : 574640985.
2 Incorrect 102 ms 19032 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 68749376.
3 Incorrect 101 ms 19144 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 145096996.
4 Incorrect 374 ms 19144 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 327860453.
5 Incorrect 371 ms 19140 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 377506838.
6 Incorrect 383 ms 19148 KB Wrong Answer: Query(200, 208) - expected : 277813445, actual : 415063604.
7 Incorrect 371 ms 19136 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 687550570.
8 Incorrect 369 ms 19388 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 145923264.
9 Incorrect 382 ms 19136 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 18757135.
10 Incorrect 368 ms 19024 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 70590726.