QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #670802 | #7685. Barkley II | Sred | WA | 153ms | 3568kb | C++17 | 1.1kb | 2024-10-24 01:50:41 | 2024-10-24 01:50:42 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e6 + 5;
const int inf = 2e6;
int f[maxn],a[maxn];
int n,m;
int lowbit(int k){
return k&(-k);
}
void add(int i,int k){
for(;i <= m*2;i += lowbit(i)) f[i] += k;
}
int find(int i){
int ans = 0;
for(;i >= 1; i-= lowbit(i)) ans += f[i];
return ans;
}
map<int,int> mp;
void solve(){
cin >> n >> m;
int ans = -1;
for(int i = 1 ;i <= n ;i ++) {
cin >> a[i];
}
for(int i = 1;i <= n ;i ++){
ans = max(ans,find(i) - find(mp[a[i]]) - a[i]);
if(mp[a[i]]) add(mp[a[i]],-1);
add(i,1);
mp[a[i]] = i;
}
for(int i = 1;i <= n;i ++){
ans = max(ans,find(n) - find(mp[a[i]]) - a[i]);
}
sort(a + 1, a + 1 + n);
for(int i = 1 ;i < n ;i ++){
if(a[i] != a[i+1] - 1){
ans = max(ans,find(n) - a[i] - 1);
break;
}
}
for(int i = 1;i <= n;i ++){
if(mp[a[i]])
add(i,-1);
mp[a[i]] = 0;
}
cout << ans <<endl;
}
signed main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
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: -100
Wrong Answer
time: 153ms
memory: 3540kb
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 3 5 8 8 6 7 9 10 12 15 9 13 17 12 12 14 12 21 15 15 18 22 20 19 20 26 22 26 31 30 17 35 39 32 39 35 33 39 41 44 43 44 40 50 47 40 48 48 53 52 51 55 46 48 60 63 66 60 55 59 71 56 67 68 71 64 79 76 74 74 72 76 80 87 81 77 90 92 87 88 91 79 82 81 99 96 98 96 99 100 99 102 98 100 100 103 98 107 105 97...
result:
wrong answer 2nd numbers differ - expected: '5', found: '3'