oj.uz

Submission #948644

# Submission time Handle Problem Language Result Execution time Memory
948644 2024-03-18T09:55:49 Z Am_pula_mare Poklon (COCI17_poklon) C++11
126 / 140
 5000 ms 10600 KB 
#include <bits/stdc++.h>

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

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
126.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 11 ms 2396 KB Output is correct
5 Correct 637 ms 4692 KB Output is correct
6 Correct 653 ms 4692 KB Output is correct
7 Correct 1779 ms 7248 KB Output is correct
8 Correct 3254 ms 9968 KB Output is correct
9 Correct 4976 ms 10600 KB Output is correct
10 Execution timed out 5023 ms 10064 KB Time limit exceeded