oj.uz

Submission #948643

# Submission time Handle Problem Language Result Execution time Memory
948643 2024-03-18T09:54:53 Z Am_pula_mare Poklon (COCI17_poklon) C++11
84 / 140
 5000 ms 10064 KB 
#include <bits/stdc++.h>

using namespace std;
int const N = 5e5 + 50;
int bucket_size = 0, n, q;
int v[N];
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
84.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 5 ms 2396 KB Output is correct
4 Correct 24 ms 2644 KB Output is correct
5 Correct 1843 ms 4696 KB Output is correct
6 Correct 2174 ms 4700 KB Output is correct
7 Execution timed out 5054 ms 6992 KB Time limit exceeded
8 Execution timed out 5062 ms 9304 KB Time limit exceeded
9 Execution timed out 5053 ms 10064 KB Time limit exceeded
10 Execution timed out 5025 ms 9968 KB Time limit exceeded