QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644748#7904. Rainbow Subarrayjty233WA 551ms13668kbC++236.9kb2024-10-16 15:22:022024-10-16 15:22:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 15:22:03]
  • 评测
  • 测评结果：WA
  • 用时：551ms
  • 内存：13668kb
查看
  • [2024-10-16 15:22:02]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

#ifndef ALGORITHM_OPT_SEARCH
#define ALGORITHM_OPT_SEARCH
// 优化查找通用算法

namespace Search
{
    const double PI = acosl(-1.);
    constexpr double INF = 1e20;
    constexpr double EPS = 1e-12;
    namespace Binary
    {
        template <typename T>
        T solve_max(T L, T R, const std::function<bool(T)> &check)
        {
            T l = L, r = R;
            bool spj = std::is_integral<T>::value;
            while (l + EPS < r)
            {
                T mid = (l + r) / 2;
                if (check(mid))
                    l = mid + spj;
                else
                    r = mid;
            }
            return (l + r) / 2;
        }
        template <typename T>
        T solve_min(T L, T R, const std::function<bool(T)> &check)
        {
            return solve_max(L, R, [&check](T x) -> bool
                             { return !check(x); }) +
                   std::is_integral<T>::value;
        }
    }
    namespace Ternary
    {
        template <typename T, typename Calc>
        T solve_max(T L, T R, const Calc&calc)
        {
            T l = L, r = R;
            while (l < r)
            {
                T midl = l + (r - l) / 3;
                T midr = r - (r - l) / 3;
                if (calc(midl) < calc(midr))
                    l = midl + 1;
                else
                    r = midr - 1;
            }
            return (l + r) / 2;
        }
        template <typename T, typename Calc>
        T solve_min(T L, T R, const Calc&calc)
        {
            return solve_max<T>(L, R, [&calc](T x) -> double
                                { return -calc(x); });
        }
    }
}

#endif

#ifndef FENWICK_TREE
#define FENWICK_TREE
// 树状数组

int lowbit(int x) { return x & -x; }

template <typename T = int>
struct BIT
{
    int n;
    std::vector<T> node;
    BIT(int n = 0) { init(n); }
    BIT(const std::vector<T> &initarr)
    {
        init(initarr);
    }
    void init(const std::vector<T> &initarr)
    {
        init(initarr.size());
        for (int i = 1; i <= n; i++)
        {
            node[i] += initarr[i - 1];
            if (i + lowbit(i) <= n)
                node[i + lowbit(i)] += node[i];
        }
    }
    void init(int n)
    {
        this->n = n;
        node.assign(n + 1, T());
    }
    void add(int k, T v)
    {
        if (!k)
            return;
        for (; k <= n; k += lowbit(k))
            node[k] += v;
    }
    T ask(int k)
    {
        T ret = 0;
        for (; k > 0; k -= lowbit(k))
            ret += node[k];
        return ret;
    }
    T ask(int l, int r)
    {
        if (l > r)
            std::swap(l, r);
        return ask(r) - ask(l - 1);
    }
    int kth(T k)
    {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i >>= 2)
        {
            if (x + i <= n && k >= node[x + i - 1])
            {
                x += i;
                k -= node[x - 1];
            }
        }
        return x;
    }
};

template <typename T = int>
struct BIT_range
{
    int n;
    BIT<T> di, dn;
    BIT_range(int n = 0) : di(n), dn(n) {}
    BIT_range(const std::vector<T> &initarr)
    {
        init(initarr);
    }
    void init(const std::vector<T> &initarr)
    {
        init(initarr.size());
        for (int i = 1; i <= n; i++)
        {
            di.node[i] += i * initarr[i - 1];
            if (i < n)
                di.node[i + 1] -= (i + 1) * initarr[i - 1];
            if (i + lowbit(i) <= n)
                di.node[i + lowbit(i)] += di.node[i];
            dn.node[i] += initarr[i - 1];
            if (i < n)
                dn.node[i + 1] -= initarr[i - 1];
            if (i + lowbit(i) <= n)
                dn.node[i + lowbit(i)] += dn.node[i];
        }
    }
    void init(int n)
    {
        this->n = n;
        di.init(n + 1);
        dn.init(n + 1);
    }
    void __add(int k, int v)
    {
        di.add(k, k * v);
        dn.add(k, v);
    }
    void add(int l, int r, T v)
    {
        if (l > r)
            std::swap(l, r);
        __add(l, v);
        __add(r + 1, -v);
    }
    void add(int k, T v) { add(k, k, v); }
    T __ask(int k)
    {
        return (k + 1) * dn.__ask(k) - di.__ask(k);
    }
    T ask(int l, int r)
    {
        if (l > r)
            std::swap(l, r);
        return __ask(r) - __ask(l - 1);
    }
};

#endif

using i64 = long long;

constexpr i64 M = 1e9 + 7;

i64 qpow(i64 x, i64 y)
{
    i64 res = 1ll;
    while (y)
    {
        if (y & 1)
            res = res * x % M;
        x = x * x % M;
        y >>= 1;
    }
    return res;
}
i64 n, k;
int a[500005];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        map<int, int> idx1;
        unordered_map<int, int> idx;
        vector<int> val(1);
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            a[i] -= i;
            if (!idx1.count(a[i]))
                idx1[a[i]] = 1;
        }
        for (auto &[k, v] : idx1)
        {
            v = ++cnt;
            idx[k] = v;
            val.push_back(k);
        }
        BIT<i64> x1(cnt + 5);
        BIT x2(cnt + 5);
        int l = 0, r = 0;
        int ans = 0;

        x1.add(idx[a[0]], a[0]);
        x2.add(idx[a[0]], 1);

        while (l < n-ans)
        {
        start:

            auto f = [&](int x) -> i64
            {
                i64 x_val = val[x];
                int lnum = x2.ask(x - 1);
                int rnum = x2.ask(x + 1, cnt);

                i64 lsum = x1.ask(x - 1);
                i64 rsum = x1.ask(x + 1, cnt);
                // cout << lnum << ' ' << lsum << ' ' << rnum << ' ' << rsum << " xval:" << x_val << endl;

                return lnum * x_val - lsum + rsum - rnum * x_val;
            };

            i64 use = Search::Ternary::solve_min<int>(1, cnt, f);
            use = f(use);
            if(use <= k) {
                ans = max(ans, r - l + 1);
            }
            if (use <= k && r+1 < n)
            {
                // cout << l << " " << r << " => " << use << endl;
                r++;
                x1.add(idx[a[r]], a[r]);
                x2.add(idx[a[r]], 1);
                goto start;
            }

            x1.add(idx[a[l]], -a[l]);
            x2.add(idx[a[l]], -1);
            l++;

            // if (r + 1 >= n)
            //     continue;
            // r++;
            // x1.add(idx[a[r]], a[r]);
            // x2.add(idx[a[r]], 1);
            while(r+1 < n && r <= l + ans){
                r++;
                x1.add(idx[a[r]], a[r]);
                x2.add(idx[a[r]], 1);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3468kb

input:

5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3

output:

4
3
5
1
1

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 551ms
memory: 13668kb

input:

11102
2 167959139
336470888 134074578
5 642802746
273386884 79721198 396628655 3722503 471207868
6 202647942
268792718 46761498 443917727 16843338 125908043 191952768
2 717268783
150414369 193319712
6 519096230
356168102 262263554 174936674 407246545 274667941 279198849
9 527268921
421436316 3613460...

output:

1
4
3
2
6
5
7
2
4
1
4
1
1
3
1
2
7
8
7
7
1
7
5
2
4
3
1
5
7
7
3
4
3
9
3
8
6
6
3
1
6
3
1
2
4
6
4
6
4
1
3
7
1
6
3
5
6
6
1
7
5
3
1
6
3
5
3
2
2
5
2
3
10
1
4
3
2
4
5
1
7
5
5
5
8
5
3
6
3
5
5
8
5
4
5
2
1
5
1
2
3
4
8
1
3
1
2
2
8
3
1
6
8
1
8
4
5
6
6
7
3
8
3
2
8
4
5
5
2
6
2
3
1
5
4
5
3
2
4
1
2
1
4
5
8
3
7
3
3
2...

result:

wrong answer 15th lines differ - expected: '2', found: '1'
English 繁體中文 简体中文

Server Time: 2024-11-30 15:37:35 | OpenSource Project