oj.uz

Submission #931137

# Submission time Handle Problem Language Result Execution time Memory
931137 2024-02-21T09:59:23 Z parlimoos Secret (JOI14_secret) C++14
0 / 100
 368 ms 12976 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "secret.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n;
vector<int> a;
int zam[4001][2][1000] , zaminf[4001];

void buildZam(int l = 0 , int r = n - 1 , int i = 1){
    int c = (r + l) >> 1 , res = a[c];
    zaminf[i] = c , zam[i][0][c] = a[c];
    if(r == l) return;
    zam[i][1][c + 1] = a[c + 1];
    for(int j = c - 1 ; j >= l ; j--) res = Secret(a[j] , res) , zam[i][0][j] = res;
    res = a[c + 1];
    for(int j = c + 2 ; j <= r ; j++) res = Secret(res , a[j]) , zam[i][1][j] = res;
    if(r > l + 1) buildZam(l , c - 1 , i << 1) , buildZam(c + 1 , r , (i << 1) | 1);
}
int getZam(int l , int r , int i){
    if(l <= zaminf[i] and r >= zaminf[i]){
        if(r == zaminf[i]) return zam[i][0][l];
        if(l == zaminf[i]) return zam[i][1][r];
        return Secret(zam[i][0][l] , zam[i][1][r]);
    }
    if(r < zaminf[i]) return getZam(l , r , i << 1);
    return getZam(l , r , (i << 1) | 1);
}
void Init(int N , int *A){
    n = N;
    for(int i = 0 ; i < n ; i++) a.pb(A[i]);
    buildZam();
}
int Query(int L , int R){
    return getZam(L , R , 1);
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 8872 KB Wrong Answer: Query(255, 409) - expected : 307522235, actual : 827471512.
2 Incorrect 98 ms 8872 KB Wrong Answer: Query(127, 153) - expected : 342921603, actual : 708520034.
3 Incorrect 95 ms 8788 KB Wrong Answer: Query(139, 140) - expected : 532639920, actual : 379416300.
4 Incorrect 356 ms 12976 KB Wrong Answer: Query(374, 396) - expected : 402362963, actual : 564777122.
5 Incorrect 352 ms 12884 KB Wrong Answer: Query(937, 999) - expected : 615241818, actual : 808540508.
6 Incorrect 352 ms 12976 KB Wrong Answer: Query(653, 654) - expected : 227441904, actual : 883702225.
7 Correct 356 ms 12876 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 364 ms 12972 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 359 ms 12884 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 368 ms 12880 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1