XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#52141 #1287. 密集火力 Accepted 100 2564 ms 3700 K C++ 11 / 795 B JamesHelium 2021-07-06 21:17:03
显示原始代码 
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <map>

typedef long long LL;
const int MaxN = 1e5 + 10;
int t[MaxN];
std::map<int, int> countl, countr;

LL search(int l, int r) {
    if (r - l <= 1) {
        return 0LL;
    }
    int mid = (l + r) / 2;
    LL ans = search(l, mid) + search(mid, r);

    countl.clear();
    countr.clear();
    for (int i = mid; i < r; ++i) {
        countr[t[i]]++;
    }
    for (int i = l; i < mid; ++i) {
        countl[t[i]]++;
    }
    for (int i = mid; i < r; ++i) {
        ans += countl[t[i]] * LL(i - mid);
    }
    for (int i = l; i < mid; ++i) {
        ans += countr[t[i]] * LL(mid - i);
    }

    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i(0); i < n; ++i) {
        scanf("%d", t + i);
    }
    printf("%lld\n", search(0, n));
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：142 ms
内存：1800 KiB

输入文件（data0.in） 

35710
846930886 1714636915 424238335 492 1189641421 1027 2059 1967513926 426 736 521595368 172695642
<269268 bytes omitted>

答案文件（data0.out） 

640460406

用户输出 

640460406

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：173 ms
内存：2004 KiB

输入文件（data1.in） 

42852
933882845 73589112 361 2183 372992966 2667 1248595624 1405151665 343 157 1513407086 2851 13479
<323205 bytes omitted>

答案文件（data1.out） 

1093228165

用户输出 

1093228165

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：205 ms
内存：2264 KiB

输入文件（data2.in） 

49994
977 541 164 2062184216 1907 149 1132 2900 2485 1108420632 526023643 2588 779 1427 1229 1343950
<378378 bytes omitted>

答案文件（data2.out） 

1730330593

用户输出 

1730330593

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：244 ms
内存：2536 KiB

输入文件（data3.in） 

57136
162152749 415393146 1488 1944 526 1777131663 1201 693488736 1111 1857115444 2060 1409741647 77
<431359 bytes omitted>

答案文件（data3.out） 

2597560277

用户输出 

2597560277

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：279 ms
内存：2820 KiB

输入文件（data4.in） 

64278
1258 233961773 1388327033 1087973118 1273 2658 1341 2102 49267988 1089 1985024021 529394549 23
<487043 bytes omitted>

答案文件（data4.out） 

3647558386

用户输出 

3647558386

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：315 ms
内存：2948 KiB

输入文件（data5.in） 

71420
600032353 989 1875 2167 599060422 2100042242 1103081139 550 2035729858 923330093 1281426848 18
<539712 bytes omitted>

答案文件（data5.out） 

5045417196

用户输出 

5045417196

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：356 ms
内存：3188 KiB

输入文件（data6.in） 

78562
1664 985 604 2030 1282962027 52842430 320460834 1378883832 2057 1817984087 2295 4 912945868 20
<594174 bytes omitted>

答案文件（data6.out） 

6697920924

用户输出 

6697920924

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：391 ms
内存：3528 KiB

输入文件（data7.in） 

85704
708 13 881 272534480 1058 473523239 1842655383 2750 703 1444765864 506 2222 932 1850553746 169
<647813 bytes omitted>

答案文件（data7.out） 

8685482323

用户输出 

8685482323

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：434 ms
内存：3700 KiB

输入文件（data8.in） 

92846
309 2841 1153457710 1657671322 945258204 2397 2831 2022 2354 171522782 1028 1408643971 1413 19
<701521 bytes omitted>

答案文件（data8.out） 

11113971698

用户输出 

11113971698

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：25 ms
内存：628 KiB

输入文件（data9.in） 

100000
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
<199907 bytes omitted>

答案文件（data9.out） 

166661666700000

用户输出 

166661666700000

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.