oj.uz

Submission #1085990

# Submission time Handle Problem Language Result Execution time Memory
1085990 2024-09-09T08:57:48 Z Icelast Secret (JOI14_secret) C++17
100 / 100
 310 ms 4516 KB 
#include "secret.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct MeowTree{
    struct Info{
        int v = 0;
    };
    struct Node{
        vector<int> lt, rt;
        int mid;
    };
    int n, N;
    vector<Node> T;
    MeowTree(int n, vector<int> a) : n(n){
        N = 1;
        while(N < n){
            N*=2;
        }
        T.resize(N*2);
        auto build = [&](auto build, int node, int low, int high) -> void{
            int mid = (low+high)/2;
            T[node].mid = mid;
            if(low == high){
                T[node].lt.push_back(a[mid]);
                return;
            }
            T[node].lt.push_back(a[mid]);
            T[node].rt.push_back(a[mid+1]);
            for(int i = mid-1; i >= low; i--){
                if(i >= n) continue;
                T[node].lt.push_back(Secret(a[i], T[node].lt.back()));
            }
            for(int i = mid+2; i <= min(n, high); i++){
                T[node].rt.push_back(Secret(T[node].rt.back(), a[i]));
            }
            build(build, node*2, low, mid);
            build(build, node*2+1, mid+1, high);
        };
        build(build, 1, 1, N);
    }
    int query(int l, int r){
        if(l == r) return T[l+N-1].lt[0];
        int low = l+N-1, high = r+N-1;
        while(low != high){
            if(low > high) swap(low, high);
            high/=2;
        }
        int node = low, mid = T[node].mid;
        return Secret(T[node].lt[mid-l], T[node].rt[r-mid-1]);
    }
};
MeowTree T(1, {1});
void Init(int n, int A[]) {
    vector<int> a(n+1);
    for(int i = 0; i < n; i++){
        a[i+1] = A[i];
    }
    T = MeowTree(n, a);
}
int Query(int l, int r) {
    l++;
    r++;
    return T.query(l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2744 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 86 ms 2648 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 84 ms 2720 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 303 ms 4516 KB Output is correct - number of calls to Secret by Init = 7991, maximum number of calls to Secret by Query = 1
5 Correct 304 ms 4436 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
6 Correct 310 ms 4392 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
7 Correct 305 ms 4516 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
8 Correct 295 ms 4432 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
9 Correct 296 ms 4516 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1
10 Correct 301 ms 4488 KB Output is correct - number of calls to Secret by Init = 8000, maximum number of calls to Secret by Query = 1