QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #573706 | #9313. Make Max | cjl000 | RE | 797ms | 46016kb | C++23 | 3.9kb | 2024-09-18 19:44:38 | 2024-09-18 19:44:38 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<math.h>
#include<string.h>
#include<deque>
#include<string>
#include<queue>
#include<cstring>
#include<string>
#include<numeric>
#include<bitset>
#include<array>
#include<stack>
using namespace std;
#define lowbit(x) x & ( -x )
#define endl '\n'
#define itn long long
#define int long long
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define ull unsigned long long
#define bug cout<<"bug"<<endl;
//const int p = 131;
const ull hx = 13331;
int dx[6] = { 0,1,0,-1 };
int dy[6] = { 1,0,-1,0 };
const int N = 10004;
int a[200005];
void tt()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int now = a[1];
map<int, set<pair<int, int>>>mp;
set<int>st;
int l = 1;
for (int i = 2; i <= n; i++)
{
if (a[i] != now)
{
st.insert(a[i - 1]);
mp[a[i - 1]].insert({ l,i - 1 });
l = i, now = a[i];
}
}
st.insert(a[n]);
mp[a[n]].insert({ l,n });
int ans = 0;
for (auto i : st)
{
for (auto t : mp[i])
{
int l = t.first, r = t.second;
//cout << l << " " << r << endl;
if (a[l] == a[l - 1])
{
auto tt = prev(mp[i].lower_bound({ l,l }));
mp[i].insert({ (*tt).first,r });
mp[i].erase(tt);
continue;
}
if (a[r] == a[r + 1])
{
auto tt = mp[i].lower_bound({ l + 1,l + 1 });
mp[i].insert({ l,(*tt).second });
mp[i].erase(tt);
}
if (l == 1)
{
if (r == n)
{
cout << ans << endl;
return;
}
int cnt = a[r + 1];
if (cnt == a[l])
continue;
auto tt = mp[cnt].lower_bound({ r + 1,r + 1 });
ans += r - l + 1;
a[l] = a[r + 1];
a[r] = a[r + 1];
mp[cnt].insert({ l,(*tt).second });
mp[cnt].erase(tt);
continue;
}
if (r == n)
{
if (l == 1)
{
cout << ans << endl;
return;
}
int cnt = a[l - 1];
if (cnt == a[l])
continue;
auto tt = prev(mp[cnt].lower_bound({ l,l }));
ans += r - l + 1;
a[r] = a[l] = (*tt).first;
mp[cnt].insert({ (*tt).first, r });
mp[cnt].erase(tt);
continue;
}
int cnt1 = a[l - 1], cnt2 = a[r + 1];
if (cnt1 == cnt2 && cnt1 == a[l])
continue;
if (cnt1 <= cnt2)
{
int cnt = cnt1;
if (cnt == a[l])
continue;
ans += r - l + 1;
auto tt = prev(mp[cnt].lower_bound({ l,l }));
a[l] = a[r] = cnt;
mp[cnt].insert({ (*tt).first, r });
mp[cnt].erase(tt);
}
else
{
int cnt = cnt2;
if (cnt == a[l])continue;
ans += r - l + 1;
auto tt = mp[cnt].lower_bound({ r + 1,r + 1 });
a[l] = a[r + 1];
a[l] = a[r] = cnt;
mp[cnt].insert({ l,(*tt).second });
mp[cnt].erase(tt);
}
}
}
cout << ans << endl;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
tt();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
4 2 1 2 2 2 2 7 1 1 1 2 2 2 2 3 1 2 3
output:
1 0 3 3
result:
ok 4 number(s): "1 0 3 3"
Test #2:
score: 0
Accepted
time: 797ms
memory: 45416kb
input:
2 198018 875421126 585870339 471894633 383529988 625397685 944061047 704695631 105113224 459022561 760848605 980735314 847376362 980571959 329939331 644635272 326439858 752879510 837384394 175179068 182094523 397239381 1199016 185143405 279638454 252374970 822030887 860312140 137248166 993229443 164...
output:
4084978 4130372
result:
ok 2 number(s): "4084978 4130372"
Test #3:
score: 0
Accepted
time: 449ms
memory: 18756kb
input:
2 195768 3086 1582 7854 5577 5243 2734 8054 4805 5686 7065 5555 2410 6240 7589 2889 3745 8094 9147 9438 1252 5497 5786 6655 4437 3933 2579 5722 9512 3117 1742 5362 2068 1853 4069 9231 1126 3991 420 2571 5517 3063 7279 8085 6111 5503 5980 50 6003 244 9684 6343 6517 1598 5223 5520 982 3932 1093 1149 7...
output:
3061429 2997931
result:
ok 2 number(s): "3061429 2997931"
Test #4:
score: 0
Accepted
time: 320ms
memory: 46016kb
input:
2 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 39 42 41 44 43 46 45 48 47 50 49 52 51 54 53 56 55 58 57 60 59 62 61 64 63 66 65 68 67 70 69 72 71 74 73 76 75 78 77 80 79 82 81 84 83 86 85 88 87 90 89 92 91 94 93 96 95 98 97 100 99...
output:
10000000000 9999900003
result:
ok 2 number(s): "10000000000 9999900003"
Test #5:
score: 0
Accepted
time: 322ms
memory: 45780kb
input:
2 200000 200000 1 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 19...
output:
19999700003 19999500006
result:
ok 2 number(s): "19999700003 19999500006"
Test #6:
score: -100
Runtime Error
input:
1000 27 373114173 854237870 229115295 303949167 146925508 596279432 662675971 828943670 913666267 642273210 864977718 57938747 337667826 311832042 518751132 911924071 931628414 438636899 404194523 247567493 293431672 743877009 323812958 366701767 976661982 731099528 757329365 267 63595569 149400190 ...