QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267226#7685. Barkley IIuroskWA 61ms36048kbC++112.1kb2023-11-27 02:29:032023-11-27 02:29:03

Judging History

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

  • [2023-11-27 02:29:03]
  • 评测
  • 测评结果：WA
  • 用时：61ms
  • 内存：36048kb
查看
  • [2023-11-27 02:29:03]
  • 提交

answer

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;

#define maxn 500005
ll n,m;
ll a[maxn];
vector<ll> v[maxn];
ll bit[maxn];
ll sum(ll r) {
    ll ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        ret += bit[r];
    return ret;
}

ll sum(ll l,ll r) {
    return sum(r) - sum(l - 1);
}

void add(ll idx,ll delta) {
    for (; idx < maxn; idx = idx | (idx + 1))
        bit[idx] += delta;
}
vector<pll> ask[maxn];
ll id[maxn];
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    for(ll i = 1;i<=n;i++) v[a[i]].pb(i);
    for(ll i = 1;i<=m;i++){
        ll last = 0;
        for(ll x : v[i]){
            if(x-1!=last+1) ask[x-1].pb({last+1,i});
            last = x;
        }
        if(n!=last+1) ask[n].pb({last+1,i});
    }
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        ll x = a[i];
        if(id[x]!=0) add(id[x],-1);
        id[x] = i;
        add(id[x],1);
        for(pll p : ask[i]){
            ans = max(ans,sum(p.fi,i)-p.sc);
        }
    }
    cout<<ans<<endl;
    for(ll i = 1;i<=m;i++) v[i].clear();
    for(ll i = 1;i<=n;i++) ask[i].clear();
    for(ll i = 1;i<=m;i++){
        if(id[i]!=0) add(id[i],-1);
        id[i] = 0;
    }
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	cin >> t;
	while(t--){
		tc();
	}
	return (0-0);
}
/**
2
5 2
1 2 3 4 5
3 1
4 2
7 3
4 3 1 10 3 8 6
4 9
3 8
4 5
**/
Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 34568kb

input:

2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: 0
Accepted
time: 57ms
memory: 32912kb

input:

50000
10 19
12 6 1 12 11 15 4 1 13 18
10 8
8 7 6 7 6 2 2 3 4 8
10 6
3 2 6 6 5 2 3 4 5 6
10 11
6 3 7 9 2 1 2 10 10 4
10 6
6 1 2 6 1 1 3 4 2 1
10 9
8 5 3 9 1 7 5 5 1 1
10 5
1 4 3 2 5 4 5 3 5 2
10 14
3 8 12 10 4 2 3 13 7 3
10 14
5 5 12 2 8 1 13 9 8 5
10 7
5 5 6 6 1 5 3 7 3 4
10 7
5 1 4 6 1 6 4 3 7 5
10...

output:

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

result:

ok 50000 numbers

Test #3:

score: -100
Wrong Answer
time: 61ms
memory: 36048kb

input:

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

output:

1
1
2
1
2
2
0
2
2
2
1
0
2
1
1
2
2
2
3
0
3
1
2
2
3
3
1
3
0
0
3
2
2
0
2
2
1
0
2
2
3
3
3
1
3
2
2
3
2
3
2
1
2
3
1
3
3
1
2
3
1
1
2
2
2
2
0
1
0
1
0
2
1
3
0
2
2
3
2
2
1
3
1
3
1
1
1
3
1
1
4
0
1
3
2
2
2
0
3
2
4
3
3
2
1
0
4
4
3
2
1
2
1
2
3
2
3
4
4
3
0
0
1
4
1
3
3
2
3
1
3
4
3
1
2
2
3
2
3
2
3
3
1
3
1
1
4
1
1
3
...

result:

wrong answer 2377th numbers differ - expected: '-1', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-05 03:41:39 | OpenSource Project