QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#706335	#7904. Rainbow Subarray	q1w2e3r4^#	RE	0ms	3660kb	C++14	4.1kb	2024-11-03 10:38:56	2024-11-03 10:38:57

Judging History

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

[2024-11-03 10:38:57]
评测

测评结果：RE
用时：0ms
内存：3660kb

查看

[2024-11-03 10:38:56]
提交

answer

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

const int MAXN = 1e6 + 10;
int T,N,K;

map<int,int> mp;
int a[MAXN];

int mid = 0;
int lsum = 0, rsum = 0;
int lcnt = 0, rcnt = 0, midcnt = 0;

int add(int x){
    if(midcnt == 0){
        mid = x;
        mp[mid] = 1;
        midcnt = 1;
        return 0;
    }
    mp[x]++;
    if(x < mid){
        lsum += x;
        lcnt++;
        if(lcnt > midcnt + rcnt){
            auto it = prev(mp.lower_bound(mid));
            int y = it->first, ycnt = it->second;
            lsum -= y * ycnt;
            lcnt -= ycnt;
            rsum += mid * midcnt;
            rcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    else if(x > mid){
        rsum += x;
        rcnt++;
        if(rcnt > midcnt + lcnt){
            auto it = mp.lower_bound(mid + 1);
            int y = it->first, ycnt = it->second;
            rsum -= y * ycnt;
            rcnt -= ycnt;
            lsum += mid * midcnt;
            lcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    else if(x == mid){
        midcnt++;
        if(lcnt > midcnt + rcnt){
            auto it = prev(mp.lower_bound(mid));
            int y = it->first, ycnt = it->second;
            lsum -= y * ycnt;
            lcnt -= ycnt;
            rsum += mid * midcnt;
            rcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        if(rcnt > midcnt + lcnt){
            auto it = mp.lower_bound(mid + 1);
            int y = it->first, ycnt = it->second;
            rsum -= y * ycnt;
            rcnt -= ycnt;
            lsum += mid * midcnt;
            lcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    assert(0);
}

int del(int x){
    mp[x]--;
    if(mp[x] == 0) mp.erase(x);
    int flag = 0;
    if(x < mid){
        lsum -= x;
        lcnt--;
        if(rcnt > midcnt + lcnt){
            auto it = mp.lower_bound(mid + 1);
            int y = it->first, ycnt = it->second;
            rsum -= y * ycnt;
            rcnt -= ycnt;
            lsum += mid * midcnt;
            lcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    else if(x > mid){
        rsum -= x;
        rcnt--;
        if(lcnt > midcnt + rcnt){
            auto it = prev(mp.lower_bound(mid));
            int y = it->first, ycnt = it->second;
            lsum -= y * ycnt;
            lcnt -= ycnt;
            rsum += mid * midcnt;
            rcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    else if(x == mid){
        midcnt--;
        if(lcnt > midcnt + rcnt){
            auto it = prev(mp.lower_bound(mid));
            int y = it->first, ycnt = it->second;
            lsum -= y * ycnt;
            lcnt -= ycnt;
            rsum += mid * midcnt;
            rcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        if(rcnt > midcnt + lcnt){
            auto it = mp.lower_bound(mid + 1);
            int y = it->first, ycnt = it->second;
            rsum -= y * ycnt;
            rcnt -= ycnt;
            lsum += mid * midcnt;
            lcnt += midcnt;
            mid = y;
            midcnt = ycnt;
        }
        return lcnt * mid - lsum + rsum - rcnt * mid;
    }
    assert(0);
}

void prepare(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> a[i];
        a[i] -= i;
    }
    int r = 0;
    int ans = 0;
    for(int i = 1; i <= N; i++){
        while(r < N){
            if(add(a[r+1]) > K){
                del(a[r+1]);
                break;
            }
            r++;
        }
        ans = max(ans, r - i + 1);
        del(a[i]);
    }
    cout << ans << "\n";
}

int main(){
    cin >> T;
    while(T--){
        prepare();
    }
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3660kb

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:

result:

ok 5 lines

Test #2:

score: -100

Runtime Error

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: