Submission #39659005
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200010], t[200010], len = 450;
struct node {
int l, r, num;
} ask[200010];
int ans[200010];
signed main() {
int n, q;
scanf("%lld%lld", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= q; i++) {
scanf("%lld%lld", &ask[i].l, &ask[i].r);
ask[i].num = i;
}
sort(ask + 1, ask + q + 1, [&](node x, node y) {
if (x.l / len != y.l / len)
return x.l / len < y.l / len;
if (x.l / len % 2 == 0) return x.r < y.r;
else return x.r > y.r;
});
int l = 1, r = 0, now = 0;
auto add = [&](int x) {
t[x]++;
if (t[x] >= 3) now += (t[x] - 1) * (t[x] - 2) / 2;
};
auto del = [&](int x) {
t[x]--;
if (t[x] >= 2) now -= t[x] * (t[x] - 1) / 2;
};
for (auto [ll, rr, num] : ask) {
while (r < rr) add(a[++r]);
while (l > ll) add(a[--l]);
while (r > rr) del(a[r--]);
while (l < ll) del(a[l++]);
ans[num] = now;
}
for (int i = 1; i <= q; i++)
printf("%ld\n", ans[i]);
return 0;
}
Submission Info
Submission Time
2023-03-12 12:26:47+0900
Task
G - Triple Index
User
cxm1024
Language
C++ (GCC 9.2.1)
Score
600
Code Size
1051 Byte
Status
AC
Exec Time
310 ms
Memory
13080 KiB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:41:13: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘long long int’ [-Wformat=]
41 | printf("%ld\n", ans[i]);
| ~~^ ~~~~~~
| | |
| long int long long int
| %lld
./Main.cpp:11:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
11 | scanf("%lld%lld", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
./Main.cpp:13:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
13 | scanf("%lld", &a[i]);
| ~~~~~^~~~~~~~~~~~~~~
./Main.cpp:15:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
15 | scanf("%lld%lld", &ask[i].l, &ask[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
600 / 600
Status
Set Name
Test Cases
Sample
example0.txt, example1.txt
All
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, example0.txt, example1.txt
Case Name
Status
Exec Time
Memory
000.txt
AC 89 ms
9944 KiB
001.txt
AC 86 ms
10008 KiB
002.txt
AC 87 ms
10012 KiB
003.txt
AC 215 ms
13076 KiB
004.txt
AC 144 ms
11628 KiB
005.txt
AC 139 ms
11624 KiB
006.txt
AC 140 ms
11612 KiB
007.txt
AC 108 ms
11572 KiB
008.txt
AC 139 ms
11588 KiB
009.txt
AC 164 ms
11532 KiB
010.txt
AC 192 ms
11684 KiB
011.txt
AC 81 ms
8024 KiB
012.txt
AC 50 ms
6616 KiB
013.txt
AC 155 ms
10656 KiB
014.txt
AC 129 ms
10536 KiB
015.txt
AC 293 ms
13080 KiB
016.txt
AC 310 ms
11484 KiB
017.txt
AC 248 ms
11548 KiB
018.txt
AC 239 ms
11540 KiB
019.txt
AC 238 ms
11416 KiB
020.txt
AC 232 ms
11444 KiB
021.txt
AC 233 ms
11380 KiB
022.txt
AC 233 ms
11532 KiB
023.txt
AC 229 ms
11576 KiB
024.txt
AC 233 ms
11496 KiB
025.txt
AC 238 ms
11492 KiB
026.txt
AC 236 ms
11528 KiB
027.txt
AC 234 ms
11628 KiB
028.txt
AC 237 ms
11636 KiB
029.txt
AC 239 ms
11508 KiB
030.txt
AC 237 ms
11524 KiB
031.txt
AC 246 ms
11388 KiB
032.txt
AC 271 ms
11444 KiB
033.txt
AC 273 ms
11508 KiB
034.txt
AC 270 ms
11492 KiB
example0.txt
AC 8 ms
3772 KiB
example1.txt
AC 7 ms
3580 KiB