#include <bits/stdc++.h>
using namespace std;
#define N 1000007
int n,q,l,r,cnt[N],a[N],ans[N],pre[3][N];
vector<pair<int,int>> b;
vector<pair<int,int>> res[N];
struct BIT {
int size;
vector<int> bit;
BIT(int n) : size(n), bit(n + 1) {}
void update(int x, int v) {
for (; x <= size; x += x & (-x)) { bit[x] += v; }
}
/** @return sum of the values in [0,b] */
int query(int b) {
int result = 0;
for (; b > 0; b -= b & (-b)) { result += bit[b]; }
return result;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
cin >> n >> q;
for (int i=1; i<=n; i++)
{
cin >> a[i];
b.push_back({a[i],i});
}
sort(b.begin(),b.end());
int tmp=1;
BIT bit(n);
a[b[0].second]=tmp;
for (int i=1; i<n; i++)
{
if(b[i].first!=b[i-1].first) tmp++;
a[b[i].second]=tmp;
}
for(int i=0; i<q; i++)
{
cin >> l >> r;
l,r;
res[r].push_back({l,i});
}
for(int i=1; i<=n; i++)
{
if (pre[1][a[i]]!=0) bit.update(pre[1][a[i]],-2);
if(pre[0][a[i]]!=0) bit.update(pre[0][a[i]],1);
// cout << pre[1][a[i]] << " " << pre[0][a[i]] << " " << a[i] << "\n";
// pre[2][a[i]]=pre[1][a[i]];
pre[1][a[i]]=pre[0][a[i]];
pre[0][a[i]]=i;
long long s=bit.query(i);
// cout << s << "\n";
for (auto c:res[i])
{
ans[c.second]=s-bit.query(c.first-1);
}
}
// cout << "\n";
for (int i=0; i<q; i++) cout << ans[i] << "\n";
return 0;
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:46:9: warning: left operand of comma operator has no effect [-Wunused-value]
46 | l,r;
| ^
poklon.cpp:46:12: warning: right operand of comma operator has no effect [-Wunused-value]
46 | l,r;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Incorrect |
11 ms |
23796 KB |
Output isn't correct |
| 3 |
Incorrect |
13 ms |
23796 KB |
Output isn't correct |
| 4 |
Incorrect |
14 ms |
23976 KB |
Output isn't correct |
| 5 |
Incorrect |
58 ms |
28332 KB |
Output isn't correct |
| 6 |
Incorrect |
56 ms |
28360 KB |
Output isn't correct |
| 7 |
Incorrect |
111 ms |
33044 KB |
Output isn't correct |
| 8 |
Incorrect |
181 ms |
37848 KB |
Output isn't correct |
| 9 |
Incorrect |
227 ms |
42556 KB |
Output isn't correct |
| 10 |
Incorrect |
290 ms |
47248 KB |
Output isn't correct |
