oj.uz

Submission #948637

# Submission time Handle Problem Language Result Execution time Memory
948637 2024-03-18T09:50:39 Z Am_pula_mare Poklon (COCI17_poklon) C++11
140 / 140
 1032 ms 13400 KB 
#include <bits/stdc++.h>

using namespace std;
int const N = 5e5 + 50;
int bucket_size = 0, n, q;
int v[N], M[N];

struct queries{
    int x, y, id, ans;
};
queries Q[N];

bool cmp(queries a, queries b){
    return (a.x / bucket_size) < (b.x / bucket_size) || ((a.x / bucket_size) == (b.x / bucket_size) && a.y <= b.y);
}

bool cmp_id(queries a, queries b){
    return a.id <= b.id;
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];

    for(int i = 1; i <= q; ++i)
    {
        cin >> Q[i].x >> Q[i].y;
        Q[i].id = i;
    }
    bucket_size = (int) (n / sqrt(q));

    sort(Q + 1, Q + q + 1, cmp);
    int l = 0, r = 0, ans = 0;

    for(int i = 1; i <= q; ++i)
    {
        while(r < Q[i].y)
        {
            ++r;
            ++M[v[r]];
            if(M[v[r]] == 2) ++ans;
            if(M[v[r]] == 3) --ans;
        }
        while(l > Q[i].x)
        {
            --l;
            ++M[v[l]];
            if(M[v[l]] == 2) ++ans;
            if(M[v[l]] == 3) --ans;
        }
        while(r > Q[i].y)
        {
            --M[v[r]];
            if(M[v[r]] == 2) ++ans;
            if(M[v[r]] == 1) --ans;
            --r;
        }
        while(l < Q[i].x)
        {
            --M[v[l]];
            if(M[v[l]] == 2) ++ans;
            if(M[v[l]] == 1) --ans;
            ++l;
        }
        Q[i].ans = ans;
    }
    sort(Q + 1, Q + q + 1, cmp_id);

    for(int i = 1; i <= q; ++i)
        cout << Q[i].ans << "\n";
    return 0;
}

Subtask #1
140.0 / 140.0

# 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 2396 KB Output is correct
5 Correct 140 ms 4696 KB Output is correct
6 Correct 146 ms 4704 KB Output is correct
7 Correct 329 ms 7132 KB Output is correct
8 Correct 543 ms 9808 KB Output is correct
9 Correct 776 ms 10472 KB Output is correct
10 Correct 1032 ms 13400 KB Output is correct