# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
610899 | racsosabe | Poklon (COCI17_poklon) | C++14 | 1026 ms | 30636 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace::std;
const int N = 500000 + 5;
const int SQRT = 710;
const int bsize = 710;
int n;
int q;
int a[N];
int L[N];
int val[N];
int block[SQRT];
int ans[N];
int last1[N];
int last2[N];
int last3[N];
vector<int> Q[N];
void compress(){
set<int> S;
for(int i = 1; i <= n; i++) S.emplace(a[i]);
int len = 0;
map<int, int> id;
for(int x : S){
id[x] = len++;
}
for(int i = 1; i <= n; i++) a[i] = id[a[i]];
}
void update(int x, int y){
int idx = x / bsize;
block[idx] += y;
val[x] += y;
}
int query(int l, int r){
int res = 0;
while(l % bsize and l <= r){
res += val[l];
l++;
}
while(l + bsize - 1 <= r){
res += block[l / bsize];
l += bsize;
}
while(l <= r){
res += val[l];
l++;
}
return res;
}
int get_sum(int pos){
return query(1, pos);
}
void fix(int i){
int x = a[i];
int l1 = last1[x], l2 = last2[x], l3 = last3[x];
if(l2){
update(l3 + 1, -1);
update(l2 + 1, 1);
}
if(l1){
update(l2 + 1, 1);
update(l1 + 1, -1);
}
last3[x] = l2;
last2[x] = l1;
last1[x] = i;
}
void download(int i){
for(int at : Q[i]){
ans[at] = get_sum(L[at]);
}
}
void solve(){
for(int i = 1; i <= n; i++){
fix(i);
download(i);
}
}
int main(){
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
compress();
for(int i = 1; i <= q; i++){
int r;
scanf("%d %d", L + i, &r);
Q[r].emplace_back(i);
}
solve();
for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |