#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
/* online submission */
#endif
ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/**************************COCI 2016-2017 R5 P4 (Alt)*************************/
struct Query {
int l, r, idx;
pii ord;
inline void calcOrder() {
ord = { l, r };
}
};
inline bool operator<(const Query &a, const Query &b) {
return a.ord < b.ord;
}
const int MAXN = 500000;
int N, M, Q, A[MAXN], nxt[MAXN], lastSeen[MAXN];
Query qs[MAXN];
int ans[MAXN];
int L = 0;
int bit[MAXN + 1];
void update(int k, int val) {
for (k++; k <= N; k += (k&-k))
bit[k] += val;
}
int query(int k) {
int temp = 0;
for (k++; k > 0; k -= (k&-k))
temp += bit[k];
return temp;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
void init() {
FOR(i, 0, M) {
int cur = lastSeen[i];
int cnt = 0;
while (cnt<3 && cur != -1) {
if (cnt == 0) update(cur, 0);
else if (cnt == 1) update(cur, 1);
else update(cur, -1);
cnt++;
cur = nxt[cur];
}
}
}
void remove(int cur) {
cur = nxt[cur];
int cnt = 0;
while (cnt<3 && cur != -1) {
if (cnt == 0) update(cur, -1);
else if (cnt == 1) update(cur, 2);
else update(cur, -1);
cnt++;
cur = nxt[cur];
}
}
void calcNext() {
fill(lastSeen, lastSeen + N, -1);
RFORE(i, N - 1, 0) {
nxt[i] = lastSeen[A[i]];
lastSeen[A[i]] = i;
}
}
void compress(int a[], int n) {
v<int> dat;
FOR(i, 0, n) dat.emplace_back(a[i]);
sort(dat.begin(), dat.end());
dat.erase(unique(dat.begin(), dat.end()), dat.end());
FOR(i, 0, n)
a[i] = lower_bound(all(dat), a[i]) - dat.begin();
M = dat.size();
}
int main() {
io();
cin >> N >> Q;
FOR(i, 0, N) cin >> A[i];
compress(A, N);
calcNext();
FOR(i, 0, Q) {
cin >> qs[i].l >> qs[i].r;
qs[i].l--, qs[i].r--;
qs[i].idx = i;
qs[i].calcOrder();
}
sort(qs, qs + Q);
init();
FOR(i, 0, Q) {
auto q = qs[i];
while (L < q.l)
remove(L++);
ans[q.idx] = query(q.l, q.r);
}
FOR(i, 0, Q) cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
10232 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10368 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10368 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10500 KB |
Output is correct |
| 5 |
Correct |
76 ms |
13756 KB |
Output is correct |
| 6 |
Correct |
82 ms |
13904 KB |
Output is correct |
| 7 |
Correct |
162 ms |
16124 KB |
Output is correct |
| 8 |
Correct |
251 ms |
18308 KB |
Output is correct |
| 9 |
Correct |
327 ms |
20572 KB |
Output is correct |
| 10 |
Correct |
399 ms |
22572 KB |
Output is correct |
