/*
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 int max2 = 102;
const int max3 = 1003;
const int max4 = 10004;
const int maxx = 500005;
const int max6 = 1000006;
const int max7 = 10000007;
const int lg2 = 7;
const int lg3 = 10;
const int lg4 = 13;
const int lg5 = 17;
const int lg6 = 20;
const int lg7 = 24;
const int lg8 = 27;
const int lg9 = 30;
const int lg18 = 60;
const int INF = 2LL * 1000000000;
/***************/
/***Additional Functions***/
int powmod(int a,int b,int mod){int res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a, int b) { while(b) b ^= a ^= b ^= a %= b; return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int is_prime(int n){if(n==1)return 0;if(n==2)return 1;if(n%2==0)return 0;for(int i=3;i<=sqrt(n);i+=2)if(n%i==0)return 0;return 1;}
int is_integer(double n){if(floor(n)==ceil(n))return 1;return 0;}
int sto_int(string s){stringstream ss(s);int n;ss>>n;return n;}
string to_string(int n){stringstream ss;ss<<n;string s=ss.str();return s;}
/**************************/
struct data {
int l, r;
int idx;
};
int n, q, arr[maxx];
pair <int, int> brr[maxx];
data query[maxx];
int D;
bool cmp (data a, data b) {
if (a.r / D == b.r / D)
return a.l < b.l;
return a.r < b.r;
}
int cnt[maxx], ans = 0;
void add (int i) {
cnt[arr[i]] ++;
if (cnt[arr[i]] == 2)
ans ++;
if (cnt[arr[i]] == 3)
ans --;
}
void del (int i) {
cnt[arr[i]] --;
if (cnt[arr[i]] == 2)
ans ++;
if (cnt[arr[i]] == 1)
ans --;
}
int 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 (int i = 1; i <= n; i++)
scanf ("%d", &arr[i]), brr[i].first = arr[i], brr[i].second = i;
sort (brr + 1, brr + n + 1);
brr[0].first = 0;
int ptr = 0;
for (int i = 1; i <= n; i++) {
if (brr[i].first != brr[i - 1].first)
ptr ++;
arr[brr[i].second] = ptr;
}
for (int i = 1; i <= q; i++)
scanf ("%d%d", &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 (int i = 1; i <= q; i++) {
int l1 = query[i - 1].l, r1 = query[i - 1].r;
int l2 = query[i].l, r2 = query[i].r;
for (int j = l1 - 1; j >= l2; j--)
add (j);
for (int j = r1 + 1; j <= r2; j++)
add (j);
for (int j = l1; j < l2; j++)
del (j);
for (int j = r1; j > r2; j--)
del (j);
ansv[query[i].idx] = ans;
}
for (int i = 1; i <= q; i++)
printf ("%d\n", ansv[i]);
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:97:72: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &arr[i]), brr[i].first = arr[i], brr[i].second = i;
^
poklon.cpp:107:67: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &query[i].l, &query[i].r), query[i].idx = i;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17716 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17716 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17716 KB |
Output is correct |
| 4 |
Correct |
6 ms |
17716 KB |
Output is correct |
| 5 |
Correct |
239 ms |
17716 KB |
Output is correct |
| 6 |
Correct |
246 ms |
17716 KB |
Output is correct |
| 7 |
Correct |
669 ms |
17716 KB |
Output is correct |
| 8 |
Correct |
1146 ms |
17716 KB |
Output is correct |
| 9 |
Correct |
1726 ms |
17716 KB |
Output is correct |
| 10 |
Correct |
2213 ms |
17716 KB |
Output is correct |
