oj.uz

Submission #948630

# Submission time Handle Problem Language Result Execution time Memory
948630 2024-03-18T09:35:37 Z andre_stan Poklon (COCI17_poklon) C++14
140 / 140
 1913 ms 21688 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6636 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 10 ms 6492 KB Output is correct
5 Correct 196 ms 10232 KB Output is correct
6 Correct 210 ms 10428 KB Output is correct
7 Correct 490 ms 14644 KB Output is correct
8 Correct 923 ms 16936 KB Output is correct
9 Correct 1365 ms 19292 KB Output is correct
10 Correct 1913 ms 21688 KB Output is correct