QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #468715 | #8050. Random Permutation | ucup-team2307 | TL | 1ms | 7772kb | C++20 | 10.3kb | 2024-07-08 23:29:10 | 2024-07-08 23:29:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
//#define int ll
vector<pair<int, int> > crit = {
{ 1, 2 },
{ 326, 4 },
{ 1608, 6 },
{ 5161, 8 },
{ 7228, 14 },
{ 21849, 16 },
{ 24564, 18 },
{ 29810, 20 },
{ 35985, 24 },
{ 38792, 26 },
{ 39055, 28 },
{ 41632, 32 },
{ 48472, 36 },
{ 49144, 38 },
{ 51772, 40 },
{ 60436, 42 },
{ 60886, 50 },
{ 61467, 52 },
{ 63619, 54 },
{ 70543, 56 },
{ 72187, 60 },
{ 72437, 62 },
{ 75024, 66 },
{ 76455, 68 },
{ 77220, 86 },
{ 86784, 92 },
{ 89046, 98 },
{ 91256, 104 },
{ 94768, 108 },
{ 95312, 112 },
{ 95915, 114 },
{ 96569, 130 },
{ 96626, 134 },
{ 99266, 140 },
{ 99723, 142 },
{ 100502, 196 },
{ 104253, 204 },
{ 107137, 252 },
{ 110618, 276 },
{ 111261, 280 },
{ 111608, 302 },
{ 112442, 306 },
{ 116957, 312 },
{ 116991, 322 },
{ 119613, 332 },
{ 120956, 370 },
{ 120977, 372 },
{ 121140, 388 },
{ 122561, 396 },
{ 123564, 400 },
{ 124067, 404 },
{ 124145, 414 },
{ 124461, 422 },
{ 124788, 444 },
{ 125020, 452 },
{ 125214, 458 },
{ 125396, 558 },
{ 126046, 564 },
{ 126302, 570 },
{ 126478, 574 },
{ 126579, 578 },
{ 126643, 584 },
{ 126766, 668 },
{ 127156, 670 },
{ 127162, 674 },
{ 128079, 682 },
{ 128131, 688 },
{ 129209, 690 },
{ 129421, 692 },
{ 129774, 712 },
{ 130308, 732 },
{ 130392, 744 },
{ 131202, 820 },
{ 131791, 822 },
{ 132070, 844 },
{ 132162, 846 },
{ 133226, 852 },
{ 133534, 880 },
{ 133671, 884 },
{ 134468, 922 },
{ 134483, 924 },
{ 134962, 944 },
{ 135083, 1050 },
{ 135219, 1180 },
{ 136017, 1302 },
{ 136177, 1432 },
{ 136344, 1534 },
{ 137144, 1704 },
{ 137923, 1808 },
{ 138662, 1976 },
{ 139071, 2104 },
{ 139831, 2214 },
{ 140110, 2406 },
{ 140622, 2544 },
{ 141443, 2648 },
{ 141471, 2906 },
{ 141688, 3230 },
{ 141859, 3374 },
{ 142036, 3816 },
{ 142140, 4000 },
{ 142659, 4124 },
{ 142925, 4228 },
{ 143069, 4330 },
{ 143194, 4436 },
{ 143580, 4584 },
{ 143776, 4830 },
{ 143964, 5546 },
{ 144205, 5652 },
{ 144268, 5806 },
{ 144369, 5936 },
{ 144408, 6534 },
{ 144877, 6848 },
{ 145153, 6974 },
{ 145382, 7764 },
{ 145455, 7880 },
{ 145609, 8212 },
{ 145884, 8470 },
{ 146009, 8664 },
{ 146137, 9200 },
{ 146167, 9318 },
{ 146350, 9434 },
{ 146409, 9536 },
{ 146472, 9648 },
{ 146515, 9832 },
{ 146521, 9940 },
{ 146546, 10224 },
{ 146602, 10346 },
{ 146645, 10674 },
{ 146917, 11300 },
{ 146922, 12142 },
{ 146948, 12332 },
{ 147085, 12436 },
{ 147118, 12544 },
{ 147150, 14806 },
{ 147164, 14996 },
{ 147226, 15536 },
{ 147287, 15726 },
{ 147458, 15852 },
{ 147541, 15956 },
{ 147558, 16328 },
{ 147619, 16466 },
{ 147697, 16574 },
{ 147708, 16932 },
{ 147727, 17220 },
{ 147765, 17344 },
{ 147776, 19902 },
{ 147851, 20670 },
{ 147897, 22320 },
{ 147981, 24212 },
{ 147994, 26418 },
{ 148031, 27066 },
{ 148040, 27380 },
{ 148046, 28152 },
{ 148069, 28530 },
{ 148101, 28800 },
{ 148114, 28922 },
{ 148141, 34578 },
{ 148158, 37242 },
{ 148173, 38010 },
{ 148215, 39736 },
{ 148231, 40504 },
{ 148270, 40618 },
{ 148276, 40728 },
{ 148287, 40892 },
{ 148315, 41010 },
{ 148331, 41246 },
{ 148361, 41348 },
{ 148368, 41486 },
{ 148379, 41634 },
{ 148419, 41760 },
{ 148430, 41984 },
{ 148444, 42106 },
{ 148445, 42458 },
{ 148477, 42568 },
{ 148493, 42674 },
{ 148510, 42846 },
{ 148524, 42954 },
{ 148608, 43082 },
{ 148648, 43194 },
{ 148688, 43330 },
{ 148706, 43770 },
{ 148712, 43890 },
{ 148713, 45854 },
{ 148720, 52516 },
{ 148753, 55010 },
{ 148760, 58850 },
{ 148794, 72542 },
{ 148801, 75036 },
{ 148812, 75166 },
{ 148814, 75684 },
{ 148816, 76600 },
{ 148822, 77048 },
{ 148833, 77154 },
{ 148836, 77272 },
{ 148843, 77436 },
{ 148853, 77538 },
{ 148869, 77744 },
{ 148872, 78256 },
{ 148875, 78398 },
{ 148886, 78536 },
{ 148891, 78644 },
{ 148910, 78840 },
{ 148932, 91980 },
{ 148937, 94472 },
{ 148939, 95462 },
{ 148948, 95650 },
{ 148962, 95856 },
{ 148965, 96926 },
{ 148971, 101628 },
{ 148972, 104122 },
{ 148981, 104224 },
{ 148982, 104350 },
{ 148983, 104510 },
{ 149003, 104638 },
{ 149013, 105006 },
{ 149016, 105962 },
{ 149037, 106070 },
{ 149049, 106188 },
{ 149055, 106350 },
{ 149072, 106478 },
{ 149089, 106702 },
{ 149090, 106866 },
{ 149104, 107592 },
{ 149106, 107696 },
{ 149113, 107834 },
{ 149114, 107980 },
{ 149126, 108088 },
{ 149132, 108232 },
{ 149138, 108354 },
{ 149150, 108508 },
{ 149152, 108776 },
{ 149162, 109836 },
{ 149174, 110076 },
{ 149188, 110182 },
{ 149190, 110288 },
{ 149192, 110464 },
{ 149198, 116996 },
{ 149203, 117124 },
{ 149205, 118616 },
{ 149214, 124830 },
{ 149218, 124936 },
{ 149223, 125054 },
{ 149224, 125218 },
{ 149249, 125330 },
{ 149261, 125442 },
{ 149270, 125544 },
{ 149297, 125734 },
{ 149314, 125942 },
{ 149339, 126588 },
{ 149351, 126690 },
{ 149354, 126868 },
{ 149358, 126980 },
{ 149370, 127102 },
{ 149397, 127220 },
{ 149405, 127418 },
{ 149409, 127520 },
{ 149422, 127622 },
{ 149423, 128016 },
{ 149442, 128124 },
{ 149448, 128262 },
{ 149462, 129274 },
{ 149472, 129584 },
{ 149478, 129730 },
{ 149485, 148992 },
{ 149488, 149176 },
{ 149497, 149284 },
{ 149508, 150832 },
{ 149516, 151014 },
{ 149529, 151122 },
{ 149530, 151348 },
{ 149534, 151528 },
{ 149539, 152472 },
{ 149545, 152660 },
{ 149550, 152768 },
{ 149551, 153368 },
{ 149560, 153648 },
{ 149564, 169700 },
{ 149571, 169880 },
{ 149580, 169998 },
{ 149596, 170120 },
{ 149605, 170228 },
{ 149607, 170338 },
{ 149613, 172236 },
{ 149622, 172516 },
{ 149628, 172656 },
{ 149647, 172764 },
{ 149653, 172880 },
{ 149659, 172990 },
{ 149663, 174150 },
{ 149669, 174264 },
{ 149671, 174492 },
{ 149673, 174624 },
{ 149681, 174728 },
{ 149683, 174860 },
{ 149684, 174998 },
{ 149698, 175302 },
{ 149709, 175452 },
{ 149715, 176592 },
{ 149718, 179306 },
{ 149720, 180382 },
{ 149727, 180530 },
{ 149734, 181202 },
{ 149736, 181682 },
{ 149742, 181794 },
{ 149751, 182290 },
{ 149755, 182444 },
{ 149758, 183562 },
{ 149759, 183752 },
{ 149763, 183928 },
{ 149772, 184034 },
{ 149779, 184148 },
{ 149786, 184794 },
{ 149791, 185164 },
{ 149797, 189974 },
{ 149798, 190280 },
{ 149803, 190486 },
{ 149806, 190836 },
{ 149813, 203660 },
{ 149818, 204030 },
{ 149828, 204152 },
{ 149830, 212648 },
{ 149842, 212766 },
{ 149845, 214486 },
{ 149855, 214826 },
{ 149858, 215000 },
{ 149860, 225568 },
{ 149863, 233352 },
{ 149876, 233498 },
{ 149880, 233610 },
{ 149886, 246274 },
{ 149890, 246492 },
{ 149896, 246598 },
{ 149904, 248334 },
{ 149907, 249190 },
{ 149908, 249536 },
{ 149910, 252206 },
{ 149912, 258450 },
{ 149918, 275916 },
{ 149922, 276268 },
{ 149929, 277754 },
{ 149932, 279158 },
{ 149937, 296620 },
{ 149941, 296976 },
{ 149948, 298040 },
{ 149957, 298152 },
{ 149961, 298276 },
{ 149968, 298490 },
{ 149970, 298600 },
{ 149971, 299510 },
{ 149978, 299638 },
{ 149984, 299742 },
{ 149991, 299864 },
{ 149998, 299992 },
{ 1000000, 300000},
};
mt19937 rng(time(0));
const int N = 3e5+100;
int n;
int p[N];
int q[N];
void gen(int k)
{
if (k > 0)
{
n = k;
for (int i=1; i<=n; i++)
p[i] = i;
shuffle(p+1, p+n+1, rng);
}
else
{
cin>>n;
for (int i=1; i<=n; i++)
cin>>p[i];
}
for (int i=1; i<=n; i++)
q[p[i]] = i;
}
int big[N];
int cnt[2*N];
int mn[2*N];
int sum = 0;
ll gans = 0;
int id = 0;
int curlen = 0;
double A = 1.1;
int L = 50;
void process(int val)
{
// if (min(val, n+1-val) == crit[id].fi)
while (min(val, n+1-val) >= crit[id].fi + n - 3e5)
curlen = crit[id++].se;
int pos = q[val];
int len = min<ll>(n, curlen*A + L);
int s = 0;
for (int j=pos+1; j<=min(n+1, pos+len); j++)
{
// cout<<s<<" ";
cnt[N+s]++;
s += 2 * (p[j] > val) - 1;
}
ll ans = 0;
s = 0;
// cout<<" : ";
for (int j=pos-1; j>=max<int>(0, pos-len); j--)
{
// cout<<s<<" ";
ans += cnt[N-s] + cnt[N-s+1];
s += 2 * (p[j] > val) - 1;
}
// cout<<" -> "<<ans<<"\n";
gans += ans*val;
s = 0;
for (int j=pos+1; j<=min(n+1, pos+len); j++)
{
cnt[N+s]--;
s += 2 * (p[j] > val) - 1;
}
// cout<<val<<" "<<ans<<" "<<gans<<endl;
}
ll solve(double a, int l)
{
A = a;
L = l;
gans = 0;
id = 0;
for (int i=1; i<=n+1-i; i++)
{
process(i);
if (i<n+1-i)
process(n+1-i);
}
return gans;
}
int naive()
{
int q = 0;
for (int l=1; l<=n; l++)
for (int r=l; r<=n; r++)
{
vector<int> v;
for (int i=l; i<=r; i++)
v.pb(p[i]);
sort(v.begin(), v.end());
q += v[(v.size()-1) / 2];
}
return q;
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
gen(-1);
// cout<<naive()<<endl;
cout<<solve(3.0, 200)<<endl;
return 0;
while (true)
{
gen(3e5);
int N = n*(n+1)/2;
cout<<solve(3.0, 50)<<endl;
return 0;
cout<<solve(10.0, 1000)<<endl;
cout<<endl;
}
return 0;
int gans = 0;
int gmx = 0;
gen(3e5);
for (int i=1; i<=n; i++)
{
int l = q[i];
for (int i=0; i<2*N; i++)
mn[i] = 1e9;
int mxcur = 0;
int s = 0;
for (int j=1; j<=l; j++)
{
cnt[N+s]++;
mn[N+s] = min(mn[N+s], j);
s += 2 * (p[j] > i) - 1;
}
int ans = 0;
for (int j=l+1; j<=n+1; j++)
{
if (mn[N+s] != int(1e9)) mxcur = max(mxcur, j-1-mn[N+s]+1);
if (mn[N+s+1] != int(1e9)) mxcur = max(mxcur, j-1-mn[N+s+1]+1);
ans += cnt[N+s] + cnt[N+s+1];
s += 2 * (p[j] > i) - 1;
}
s = 0;
for (int j=1; j<=l; j++)
{
cnt[N+s]--;
s += 2 * (p[j] > i) - 1;
}
gans += ans * i;
// cout<<i<<" "<<ans<<"\n";
sum += mxcur;
if (mxcur > gmx && (mxcur > gmx + 100 || mxcur < 1000))
{
cout<<"{ "<<i<<", "<<mxcur<<" },"<<endl;
gmx = mxcur;
}
}
cout<<gans<<"\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7772kb
input:
4 1 4 2 3
output:
22
result:
ok 1 number(s): "22"
Test #2:
score: -100
Time Limit Exceeded
input:
100000 56449 21738 74917 44834 36187 96576 37204 28451 3444 13029 66039 8955 51445 30706 27229 37159 66052 16691 70389 29935 44984 3648 75082 73600 76621 28345 5298 37940 49412 85260 92029 18185 84398 10233 79227 98312 96649 30680 65206 38879 75397 26951 11294 58085 37297 97167 59252 44104 4058 3796...