oj.uz

Submission #643656

# Submission time Handle Problem Language Result Execution time Memory
643656 2022-09-22T17:43:59 Z pls33 Secret (JOI14_secret) C++17
0 / 100
 485 ms 4988 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

map<p32, int> queries;
vvi32 dst;

int leading_bit(int i)
{
    return 31 - __builtin_clz(i);
}

int secret_wrapper(int l, int r);

void Init(int n, int a[])
{
    dst = vvi32(leading_bit(n) + 1, vi32(n + 1));

    for (size_t row = 0; row < dst.size(); row++)
    {
        int length = 1 << row;

        for (size_t center = length; center < n + length; center += 2 * length)
        {
            int val = 0;
            for (size_t i = center; i < center + length && i <= n; i++)
            {
                dst[row][i] = val;
                if (i != n)
                {
                    val = secret_wrapper(val, a[i]);
                }
            }

            for (int i = min(size_t(n) - 1, center - 1); i >= center - length && i >= 0; i--)
            {
                dst[row][i] = secret_wrapper(dst[row][i + 1], a[i]);
            }
        }
    }
}

int Query(int l, int r)
{
    r++;
    int row = leading_bit(l ^ r);
    return secret_wrapper(dst[row][l], dst[row][r]);
}

int secret_wrapper(int l, int r)
{
    auto it = queries.find({l, r});

    int val = 0;
    if (it != queries.end())
    {
        val = it->second;
    }
    else
    {
        val = Secret(l, r);
        queries[{l, r}] = val;
    }

    return val;
}

Compilation message

secret.cpp:6: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    6 | #pragma region dalykai
      | 
secret.cpp:29: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   29 | #pragma endregion
      | 
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:49:45: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         for (size_t center = length; center < n + length; center += 2 * length)
      |                                      ~~~~~~~^~~~~~~~~~~~
secret.cpp:52:62: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |             for (size_t i = center; i < center + length && i <= n; i++)
      |                                                            ~~^~~~
secret.cpp:55:23: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |                 if (i != n)
      |                     ~~^~~~
secret.cpp:61:60: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int i = min(size_t(n) - 1, center - 1); i >= center - length && i >= 0; i--)
      |                                                          ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 2612 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854011.
2 Incorrect 133 ms 2756 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 115 ms 2752 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 162768982.
4 Incorrect 452 ms 4936 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 546373765.
5 Incorrect 453 ms 4892 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 707448136.
6 Incorrect 485 ms 4960 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 278446241.
7 Incorrect 449 ms 4872 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 54559803.
8 Incorrect 446 ms 4940 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 822146056.
9 Incorrect 440 ms 4912 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 408296780.
10 Incorrect 468 ms 4988 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 67347979.