QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#321295#7904. Rainbow SubarrayhazeWA 123ms6364kbC++232.4kb2024-02-04 13:10:052024-02-04 13:10:07

Judging History

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

  • [2024-06-09 00:00:26]
  • hack成功,自动添加数据
  • (/hack/652)
  • [2024-02-04 13:10:07]
  • 评测
  • 测评结果:WA
  • 用时:123ms
  • 内存:6364kb
  • [2024-02-04 13:10:05]
  • 提交

answer

/*
 Rainbow Subarray
 https://codeforces.com/gym/104901/problem/K
 Author: haze
*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll read() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;

struct DS{
    multiset<ll>sl, sr;
    ll suml, sumr;
    DS(){suml = sumr = 0;}
    void adjust(){
        ll n = sl.size() + sr.size();// l fl n / 2, r ce n / 2;
        while(sl.size() < n / 2){
            suml += *sr.begin();
            sumr -= *sr.begin();
            sl.emplace(*sr.begin());
            sr.erase(sr.begin());
        }
        while(sl.size() > n / 2){
            sumr += *(-- sl.end());
            suml -= *(-- sl.end());
            sr.emplace(*(-- sl.end()));
            sl.erase(-- sl.end());
        }
    }
    void insert(ll x){
        if(sr.empty() || x >= *sr.begin()){
            sr.emplace(x);
            sumr += x;
        }
        else{
            sl.emplace(x);
            suml += x;
        }
        adjust();
    }
    void del(ll x){
        if(sl.contains(x)){
            suml -= x;
            sl.erase(sl.find(x));
        }
        if(sr.contains(x)){
            sumr -= x;
            sr.erase(sr.find(x));
        }
        adjust();
    }
};

void solve() {
    ll n = read(), k = read();
    vector<ll>a(n);
    irep(i, 0, n - 1)
        a[i] = read() - i;
    ll ans = 0;
    ll l = 0, r = 0;
    DS u;
    while(r <= n){
        ll sr = u.sumr - u.suml;
        if((r - l) % 2 == 1)sr -= *u.sr.begin();
        if(sr <= k){
            ans = max(ans, r - l);
            u.insert(a[r ++]);
        }
        else{
            u.del(a[l ++]);
        }
    }
    cout << min(ans, n) << '\n';
}

int main() {
    // IOS
    int T = read();
    while (T--) {
        solve();
    }
    return 0;
}
//7 1 3 2 0 6 1

详细

Test #1:

score: 100
Accepted
time: 0ms
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
Wrong Answer
time: 123ms
memory: 6364kb

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:

wrong answer 11101st lines differ - expected: '40384', found: '40385'