#include<bits/stdc++.h>
#include <iomanip>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);
#define ll int //long long
#define for_t ll T;cin>>T;while(T--)
#define endl "\n"
#define F(a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define pb push_back
#define lc(curr) (curr * 2)
#define rc(curr) ((curr * 2) + 1)
const int maxn = 500005;
ll a[maxn];
ll tree[maxn * 4];
ll arr[maxn];
ll rightv[maxn];
vector<pair<ll,ll>> queries;
map<ll,ll> cnt;
map<ll,ll> occ;
//index of next occurrence of this element;
//generate array for all elements
//one by one remove elements from 0 to n
//once element is removed
//update tht index -> 0
//index of next occurrence of that element -> 0
//index of 2nd next occurrence of that element -> 1
//index of 3rd next occurrence of that element -> -1
//all other occurrences should be 0?
void build(ll curr,ll l,ll r)
{
if(l == r)
{
tree[curr] = arr[l];
return;
}
build(lc(curr),l,(l + r)/2);
build(rc(curr),((l + r)/2) + 1,r);
tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}
void update(ll curr,ll l,ll r,ll i,ll num)
{
if(l > i || r < i)
{
return;
}
if(l == r)
{
tree[curr] = num;
return;
}
update(lc(curr),l,(l + r)/2,i,num);
update(rc(curr),((l + r)/2),r,i,num);
tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}
ll query(ll curr,ll l,ll r,ll i,ll j)
{
if(l > j || r < i)
{
return 0;
}
if(l >= i && r <= j)
{
return tree[curr];
}
return query(lc(curr),l,(l + r)/2,i,j) + query(rc(curr),((l + r)/2) + 1,r,i,j);
}
void sol()
{
ll n,q;
cin >> n >> q;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
queries.resize(q);
for(int i = 0;i < q;i++)
{
cin >> queries[i].first >> queries[i].second;
}
memset(rightv,0,sizeof(rightv));
memset(tree,0,sizeof(tree));
memset(arr,0,sizeof(arr));
sort(all(queries));
for(int i = n;i >= 1;i--)
{
if(occ[a[i]] > 0)
{
rightv[i] = occ[a[i]];
}
else
{
rightv[i] = 0;
}
occ[a[i]] = i;
}
for(int i = 1;i <= n;i++)
{
cnt[a[i]]++;
if(cnt[a[i]] > 1)
{
continue;
}
bool temp = false;
if(rightv[i] != inf)
{
arr[i] = 0;
arr[rightv[i]] = 1;
if(rightv[rightv[i]] != inf)
{
arr[rightv[rightv[i]]] = -1;
}
}
}
build(1,1,n);
for(int i = 0;i < queries.size();i++)
{
ll l = queries[i].first;
ll r = queries[i].second;
if(i && queries[i].first != queries[i - 1].first)//have to update for new values
{
if(rightv[l] != inf)
{
update(1,1,n,l,0);
update(1,1,n,rightv[l],1);
if(rightv[rightv[l]] != inf)
{
update(1,1,n,rightv[rightv[l]],-1);
}
}
}
cout << query(1,1,n,l,r) << endl;
}
}
int main()
{
//freopen("mootube.in", "r", stdin);
//freopen("mootube.out", "w", stdout);
FIO
sol();
}
Compilation message
poklon.cpp: In function 'void sol()':
poklon.cpp:113:14: warning: unused variable 'temp' [-Wunused-variable]
113 | bool temp = false;
| ^~~~
poklon.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int i = 0;i < queries.size();i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
343 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
300 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
310 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
250 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
344 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
349 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
390 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
429 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
493 ms |
524288 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
620 ms |
524288 KB |
Execution killed with signal 9 |
