// Implementation practice (Have seen the editorial)
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cerr << #a << ": " << (a) << "\n"
#define RUNTIME prinf("%lf\n",(double)clock()/CLOCKS_PER_SEC);
typedef long long ll;
const int N = int(5e5) + 10;
int n, sq, q;
int a[N];
int cnt[N];
int answer[N];
struct query {
int id, l, r, ans;
query() {cin >> l >> r; l--; r--;}
bool operator < (query& q2) {
return r < q2.r;
}
};
vector<query> blk[1000];
int main() {
/*freopen("out", "w", stdout);
freopen("in", "r", stdin);*/
ios::sync_with_stdio(false);cin.tie(NULL);
cin >> n >> q;
sq = (int)sqrt(n + 0.5);
vector<int> tmp(n);
for (int i = 0; i < n; i++) cin >> a[i], tmp[i] = a[i];
sort(tmp.begin(), tmp.end());
for (int i = 0; i < n; i++)
a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin();
for (int i = 0; i < q; i++) {
query qq; qq.id = i;
blk[qq.l/sq].push_back(qq);
}
for (int i = 0; i < 1000; i++)
sort(blk[i].begin(), blk[i].end());
for (int bi = 0; bi < 1000; bi++) {
vector<query>& blkq = blk[bi];
int l = sq*bi, r = sq*bi, qi = 0, totq = blkq.size();
int ans = 0;
memset(cnt, 0, sizeof cnt);
for (; r < n; r++) {
cnt[a[r]]++;
if (cnt[a[r]] == 2) ans++;
if (cnt[a[r]] == 3) ans--;
while (qi < totq && r == blkq[qi].r) {
debug(r);
while (l != blkq[qi].l) {
debug(l);
if (l < blkq[qi].l) {
cnt[a[l]]--;
if (cnt[a[l]] == 1) ans--;
else if (cnt[a[l]] == 2) ans++;
l++;
}
else {
l--;
cnt[a[l]]++;
if (cnt[a[l]] == 2) ans++;
else if (cnt[a[l]] == 3) ans--;
}
}
answer[blkq[qi].id] = ans;
qi++;
}
}
}
for (int i = 0; i < q; i++) cout << answer[i] << endl;
//RUNTIME
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
113 ms |
2296 KB |
Output isn't correct |
| 2 |
Incorrect |
144 ms |
2556 KB |
Output isn't correct |
| 3 |
Incorrect |
171 ms |
2624 KB |
Output isn't correct |
| 4 |
Incorrect |
831 ms |
3812 KB |
Output isn't correct |
| 5 |
Execution timed out |
5023 ms |
14348 KB |
Time limit exceeded |
| 6 |
Execution timed out |
5034 ms |
15780 KB |
Time limit exceeded |
| 7 |
Execution timed out |
5043 ms |
22124 KB |
Time limit exceeded |
| 8 |
Execution timed out |
5038 ms |
30236 KB |
Time limit exceeded |
| 9 |
Execution timed out |
5023 ms |
40796 KB |
Time limit exceeded |
| 10 |
Execution timed out |
5019 ms |
52264 KB |
Time limit exceeded |
