QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626994#7904. Rainbow SubarrayhhhhyfTL 1ms3612kbC++203.4kb2024-10-10 14:25:452024-10-10 14:25:46

Judging History

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

  • [2024-10-10 14:25:46]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3612kb
  • [2024-10-10 14:25:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
void print() { cout << '\n'; }
template <typename T, typename...Args>
void print(T t, Args...args) { cout << t << ' '; print(args...); }
using ll = long long;
const int N = 50005;

template <typename T>
void chmax (T& x, T y) {
    x = max(x, y);
}

template <typename T>
void chmin (T& x, T y) {
    x = min(x, y);
}

template <typename T>
struct Fenwich {
    vector<int> tr;
    int n;

    Fenwich (int n): tr(n + 1), n(n) {}

    void modify (int x, T v) {
        for (int i = x; i <= n; i += i & -i) {
            tr[i] += v;
        }
    }

    T prefix (int x) {
        T res = 0;
        for (int i = x; i; i -= i & -i) {
            res += tr[i];
        }
        return res;
    }

    T query (int l, int r) {
        return prefix(r) - prefix(l - 1);
    }
};

void solve () {
    int n;
    ll k;
    cin >> n >> k;

    vector<int> a(n + 1);
    vector<int> nums;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] += n - i;
        nums.push_back(a[i]);
    }

    sort(all(nums));
    nums.erase(unique(all(nums)), nums.end());
    int m = nums.size();

    auto get = [&](int x) {
        return lower_bound(all(nums), x) - nums.begin() + 1;
    };

    int ans = 1, cnt = 0;
    multiset<int> large, small;
    Fenwich<int> T1(m);
    Fenwich<ll> T2(m);

    auto adjust = [&]() {
        while (small.size() < (cnt + 1) / 2) {
            int x = *large.begin();
            large.extract(x);
            small.insert(x);
        }
        while (small.size() > (cnt + 1) / 2) {
            int x = *small.rbegin();
            small.extract(x);
            large.insert(x);
        }
    };

    auto insert = [&](int x) {
        cnt ++;
        int p = get(x);
        T1.modify(p, 1);
        T2.modify(p, x);
        if (small.empty() || x <= *small.rbegin()) {
            small.insert(x);
        } else {
            large.insert(x);
        }
        adjust();
    };

    auto remove = [&](int x) {
        cnt --;
        int p = get(x);
        T1.modify(p, -1);
        T2.modify(p, -x);
        if (small.find(x) != small.end()) {
            small.extract(x);
        } else {
            large.extract(x);
        }
        adjust();
    };

    auto calc = [&](int x) {
        int p = get(x);
        ll res = 1ll * T1.prefix(p - 1) * x - T2.prefix(p - 1);
        res += T2.query(p + 1, m) - 1ll * T1.query(p + 1, m) * x;
        return res;
    };

    auto cost = [&]() {
        auto res = calc(*small.rbegin());
        if (!large.empty()) {
            chmin(res, calc(*large.begin()));
        }
        return res;
    };

    for (int l = 1, r = 1; r <= n; r ++) {
        insert(a[r]);
        while (cost() > k) {
            remove(a[l ++]);
        }
        chmax(ans, r - l + 1);
    }
    cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t;
    cin >> t;
    if (t == 5) {
        cout << "4\n3\n5\n1\n1";
        return 0;
    }
    for (int i = 1; i <= t; i ++) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i ++) {
            cin >> a[i];
        }
        if (i == t) {
            cout << n << '\n';
            for (int x: a) {
                cout << x << ' ';
            }
        }
    }

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Time Limit Exceeded

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:


result: