/*
ID: barish21
LANG: C++14
TASK: test
*/
/****Author: Barish Namazov****/
#include <bits/stdc++.h>
using namespace std;
/***TEMPLATE***/
#define intt long long
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define IO ios_base::sync_with_stdio(false);cin.tie();
const intt max1 = 11;
const intt max2 = 102;
const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 1000005;
const intt max6 = 1000006;
const intt max7 = 10000007;
const intt lg2 = 7;
const intt lg3 = 10;
const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;
const intt lg7 = 24;
const intt lg8 = 27;
const intt lg9 = 30;
const intt lg18 = 60;
const intt INF = 2LL * 1000000000;
/***************/
/***Additional Functions***/
intt powmod(intt a,intt b,intt mod){intt res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
intt gcd(intt a, intt b) { while(b) b ^= a ^= b ^= a %= b; return a;}
intt lcm(intt a,intt b){return a*b/gcd(a,b);}
intt is_prime(intt n){if(n==1)return 0;if(n==2)return 1;if(n%2==0)return 0;for(intt i=3;i<=sqrt(n);i+=2)if(n%i==0)return 0;return 1;}
intt is_integer(double n){if(floor(n)==ceil(n))return 1;return 0;}
intt sto_int(string s){stringstream ss(s);intt n;ss>>n;return n;}
string to_string(intt n){stringstream ss;ss<<n;string s=ss.str();return s;}
/**************************/
struct data {
intt l, r;
intt idx;
};
intt n, q, arr[maxx];
pair <intt, intt> brr[maxx];
data query[maxx];
intt D;
bool cmp (data a, data b) {
if (a.r / D == b.r / D)
return a.l < b.l;
return a.r < b.r;
}
intt cnt[maxx], ans = 0;
void add (intt i) {
cnt[arr[i]] ++;
if (cnt[arr[i]] == 2)
ans ++;
if (cnt[arr[i]] == 3)
ans --;
}
void del (intt i) {
cnt[arr[i]] --;
if (cnt[arr[i]] == 2)
ans ++;
if (cnt[arr[i]] == 1)
ans --;
}
intt ansv[maxx];
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ofstream fout ("test.out");
//ifstream fin ("test.in");
IO;
cin >> n >> q;
D = sqrt (n);
for (intt i = 1; i <= n; i++)
cin >> arr[i], brr[i].first = arr[i], brr[i].second = i;
sort (brr + 1, brr + n + 1);
brr[0].first = 0;
intt ptr = 0;
for (intt i = 1; i <= n; i++) {
if (brr[i].first != brr[i - 1].first)
ptr ++;
arr[brr[i].second] = ptr;
}
for (intt i = 1; i <= q; i++)
cin >> query[i].l >> query[i].r, query[i].idx = i;
sort (query + 1, query + q + 1, cmp);
query[0].l = query[1].l, query[0].r = query[1].l - 1;
for (intt i = 1; i <= q; i++) {
intt l1 = query[i - 1].l, r1 = query[i - 1].r;
intt l2 = query[i].l, r2 = query[i].r;
for (intt j = l1 - 1; j >= l2; j--)
add (j);
for (intt j = r1 + 1; j <= r2; j++)
add (j);
for (intt j = l1; j < l2; j++)
del (j);
for (intt j = r1; j > r2; j--)
del (j);
ansv[query[i].idx] = ans;
}
for (intt i = 1; i <= q; i++)
cout << ansv[i] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
64752 KB |
Output is correct |
| 2 |
Correct |
3 ms |
64752 KB |
Output is correct |
| 3 |
Correct |
6 ms |
64752 KB |
Output is correct |
| 4 |
Correct |
6 ms |
64752 KB |
Output is correct |
| 5 |
Correct |
366 ms |
64752 KB |
Output is correct |
| 6 |
Correct |
356 ms |
64752 KB |
Output is correct |
| 7 |
Runtime error |
0 ms |
0 KB |
-1: Interrupted system call
|
| 8 |
Runtime error |
1249 ms |
64752 KB |
Execution timed out (wall clock limit exceeded) |
| 9 |
Runtime error |
1799 ms |
64752 KB |
Execution timed out (wall clock limit exceeded) |
| 10 |
Runtime error |
2279 ms |
64752 KB |
Execution timed out (wall clock limit exceeded) |
