//******************/
//* I<3 C++ */
//* I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S INTERESTING*/
//* I LOVE PROGRAM!*/
//* IN CONTESTS */
//* GET SCORE */
//* AC CODE */
//* LET'S */
//* GO */
//* Written by: */
//* Duc Minh */
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define file(name) freopen(name".inp", "r", stdin);\
freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define endl "\n"
#define all1(a) a+1,a+n+1
#define unordered_map map
// #define push_back emplace_back
// #define gcd(a,b) __gcd(a,b);
// #define lcm(a,b) (a*b)/gcd(a,b);
const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;
const long long MODD = 2024; /// 998244353
const long long maxN = 5e5+12;
const int LOG = 700;
const int mlift = 58;
template<class A> inline int __lg(A &a) { return static_cast<int>(log2(a));}
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=MOD) a-=MOD;}
template<class A,class B> inline void minus(A &a,B b) { a-=b;while (a>=MOD) a-=MOD;while (a<0) a+=MOD;}
///--------------------------------
void solve();
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
file("ducminh");
#endif
// file("BAI4");
long long t;
// cin >> t;
t=1;
while (t--){
solve();
}
cerr << "Time elapsed: " << TIME << "s.\n";
cerr << "ducminh" << "\n";
return 0;
}
///--------------------[PROBLEM SOLUTION]--------------------///
int a[maxN],cur=0,n,q,ans[maxN],block;
int _left, _right;
int mm[maxN];
struct Query {
int l, r, pos;
};
Query queries[maxN];
bool cmp(Query x, Query y) {
return (make_pair(x.l / block, x.r) < make_pair(y.l / block, y.r));
}
void add(int pos) {
if(pos == 0) return;
int x = a[pos];
if(mm[x] == 2) cur--;
mm[x]++;
if(mm[x] == 2) cur++;
}
void erase(int pos) {
if(pos == 0) return;
int x = a[pos];
if(mm[x] == 2) cur--;
mm[x]--;
if(mm[x] == 2) cur++;
}
void mo(int i){
int left = queries[i].l, right = queries[i].r;
while (_left<left){
erase(_left);
_left++;
}
while (_left>left){
add(_left-1);
_left--;
}
while (_right>right){
erase(_right);
_right--;
}
while (_right<right){
add(_right+1);
_right++;
}
}
void solve(){
cin >> n >> q;
block=(int)sqrt(n);
for (int i=1; i<=n; i++){
cin >> a[i];
}
for (int i=1; i<=q; i++){
cin >> queries[i].l >> queries[i].r;
queries[i].pos=i;
}
sort(queries+1,queries+q+1,cmp);
for (int i=1; i<=q; i++){
mo(i);
ans[queries[i].pos]=cur;
}
for (int i=1; i<=q; i++){
cout << ans[i] << "\n";
}
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:40:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | #define file(name) freopen(name".inp", "r", stdin);\
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:78:9: note: in expansion of macro 'file'
78 | file("ducminh");
| ^~~~
poklon.cpp:41:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:78:9: note: in expansion of macro 'file'
78 | file("ducminh");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
