oj.uz

Submission #1085974

# Submission time Handle Problem Language Result Execution time Memory
1085974 2024-09-09T08:41:20 Z Icelast Secret (JOI14_secret) C++17
0 / 100
 308 ms 4692 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--){
                T[node].lt.push_back(Secret(T[node].lt.back(), a[i]));
            }
            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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 2640 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 77 ms 2896 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 79 ms 2804 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 162768982.
4 Incorrect 307 ms 4692 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 546373765.
5 Incorrect 296 ms 4688 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 707448136.
6 Incorrect 308 ms 4544 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 302576192.
7 Incorrect 306 ms 4688 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 54559803.
8 Incorrect 301 ms 4692 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 822146056.
9 Incorrect 303 ms 4636 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 408296780.
10 Incorrect 296 ms 4692 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 67347979.