# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
917414 |
2024-01-28T05:50:57 Z |
12345678 |
Poklon (COCI17_poklon) |
C++17 |
|
943 ms |
24540 KB |
#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5, rx=720;
int n, q, v[nx], cnt[nx], t, l, r, rt, ans[nx], res;
map<int, int> mp;
vector<tuple<int, int, int>> d[rx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>v[i], mp[v[i]]=0;
for (auto &[x, y]:mp) y=++t;
for (int i=1; i<=n; i++) v[i]=mp[v[i]];
rt=sqrt(n)+1;
for (int i=1; i<=q; i++) cin>>l>>r, d[r/rt].push_back({l, r, i});
for (int i=0 ; i<=rt; i++)
{
sort(d[i].begin(), d[i].end());
l=1;
r=0;
for (auto [cl, cr, idx]:d[i])
{
while (r<cr) r++, res-=(cnt[v[r]]==2), cnt[v[r]]++, res+=(cnt[v[r]]==2);
while (r>cr) res-=(cnt[v[r]]==2), cnt[v[r]]--, res+=(cnt[v[r]]==2), r--;
while (l<cl) res-=(cnt[v[l]]==2), cnt[v[l]]--, res+=(cnt[v[l]]==2), l++;
while (l>cl) l--, res-=(cnt[v[l]]==2), cnt[v[l]]++, res+=(cnt[v[l]]==2);
//cout<<cl<<' '<<cr<<' '<<res<<' '<<cnt[1]<<'\n';
ans[idx]=res;
}
for (int j=1; j<=n; j++) cnt[j]=res=0;
}
for (int i=1; i<=q; i++) cout<<ans[i]<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
5 ms |
2652 KB |
Output is correct |
5 |
Correct |
101 ms |
6548 KB |
Output is correct |
6 |
Correct |
108 ms |
6492 KB |
Output is correct |
7 |
Correct |
279 ms |
11184 KB |
Output is correct |
8 |
Correct |
483 ms |
15700 KB |
Output is correct |
9 |
Correct |
671 ms |
20192 KB |
Output is correct |
10 |
Correct |
943 ms |
24540 KB |
Output is correct |