Submission #948897

#	Time	Username	Problem	Language	Result	Execution time	Memory
948897		andrei_marciuc	Poklon (COCI17_poklon)	C++14	140 / 140	1829 ms	21624 KiB

poklon

#include <iostream>
#include <algorithm>
#include <map>
 
using namespace std;
 
const int BUCKET = 707;
 
const int N = 5e5;
int a[N + 1], sol[N + 1], f[N + 1];
 
int n, l = 1, r, ans, q;
 
struct ceva
{
    int x, y, ind;
    bool operator < (const ceva &a)const {
        if ((x / BUCKET) == (a.x / BUCKET))
            return y < a.y;
        return (x / BUCKET) < (a.x / BUCKET);
    }
} query[N + 1];
 
void mo (int &l, int &r, int newl, int newr, int ind)
{
    while (l < newl)
    {
        if (f[a[l]] == 2)
            --ans;
        f[a[l]]--;
        if (f[a[l]] == 2)++ans;
        l++;
    }
    while (l > newl)
    {
        l--;
        if (f[a[l]] == 2)--ans;
        f[a[l]]++;
        if (f[a[l]] == 2)
            ++ans;
    }
    while (r > newr)
    {
        if (f[a[r]] == 2)
            --ans;
        f[a[r]]--;
        if (f[a[r]] == 2)++ans;
        --r;
    }
    while (r < newr)
    {
        ++r;
        if (f[a[r]] == 2)
            --ans;
        f[a[r]]++;
        if (f[a[r]] == 2)
            ++ans;
    }
    sol[ind] = ans;
}
 
int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= q; ++i)
        cin >> query[i].x >> query[i].y, query[i].ind = i;
  
    sort (query + 1, query + q + 1);
  
    for (int i = 1; i <= q; ++i)
        mo(l, r, query[i].x, query[i].y, query[i].ind);
  
    for (int i = 1; i <= q; ++i)
        cout << sol[i] << '\n';
    return 0;
}

• Subtask 1: 140 / 140