QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#644843#7904. Rainbow Subarrayjty233AC ✓770ms57628kbC++237.2kb2024-10-16 15:35:272024-10-16 15:35:30

Judging History

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

  • [2024-10-16 15:35:30]
  • 评测
  • 测评结果：AC
  • 用时：770ms
  • 内存：57628kb
查看
  • [2024-10-16 15:35:27]
  • 提交

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(int x)
    {
        int t=0;
        for(int i=19;i>=0;i--)
        {
            t+=1<<i;
            if(t>n||node[t]>=x) t-=1<<i;
            else x-=node[t];
        }
        return t+1;
    }
};

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);

        // cout << "add: " << idx[a[0]] << endl;

        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);
            i64 use = x2.kth((r-l+2)/2);
            // cout << "kth: " << (r-l+1)/2 << " => " << use << endl;
            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);
                // cout << "add: " << idx[a[r]] << endl;
                goto start;
            }

            x1.add(idx[a[l]], -a[l]);
            x2.add(idx[a[l]], -1);
            // cout << "add: " << idx[a[l]] << endl;
            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+1 <= l + ans){
                r++;
                x1.add(idx[a[r]], a[r]);
                x2.add(idx[a[r]], 1);
                // cout << "add: " << idx[a[r]] << endl;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3560kb

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: 0
Accepted
time: 220ms
memory: 13692kb

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
2
2
7
8
7
7
1
7
6
2
4
3
1
6
7
7
3
4
3
9
3
8
6
6
3
1
6
3
1
2
4
6
4
6
4
1
4
7
1
6
3
5
6
6
1
7
5
3
1
6
4
5
3
2
2
6
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
2
3
3
4
8
1
3
1
2
2
8
3
1
6
8
1
8
4
5
6
6
8
4
8
3
2
8
4
5
6
2
6
2
4
1
5
4
5
3
2
4
1
2
1
4
5
8
3
7
3
3
3...

result:

ok 11102 lines

Test #3:

score: 0
Accepted
time: 659ms
memory: 57584kb

input:

1
500000 17244641009859
54748096 75475634 204928248 276927808 84875072 103158867 27937890 322595515 186026685 45468307 69240390 139887597 188586447 373764525 121365644 310156469 185188306 60350786 211308832 384695957 370562147 208427221 35937909 267590963 126478310 275357775 55361535 335993561 36696...

output:

172998

result:

ok single line: '172998'

Test #4:

score: 0
Accepted
time: 770ms
memory: 57628kb

input:

1
500000 43483524125987
923264237 374288891 535590429 751244358 124321145 232930851 266089174 543529670 773363571 319728747 580543238 582720391 468188689 490702144 598813561 138628383 284660056 733781508 155605777 931759705 245485733 723534730 257812292 794937524 596788519 188451996 981010588 144836...

output:

174260

result:

ok single line: '174260'

Test #5:

score: 0
Accepted
time: 243ms
memory: 57564kb

input:

1
499999 62499749999
496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081 496813081...

output:

499998

result:

ok single line: '499998'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-11-30 10:36:45 | 开源项目