oj.uz

Submission #948897

# Submission time Handle Problem Language Result Execution time Memory
948897 2024-03-18T16:01:39 Z andrei_marciuc Poklon (COCI17_poklon) C++14
140 / 140
 1829 ms 21624 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 6488 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 8 ms 6492 KB Output is correct
5 Correct 184 ms 10228 KB Output is correct
6 Correct 187 ms 10240 KB Output is correct
7 Correct 474 ms 14416 KB Output is correct
8 Correct 866 ms 16968 KB Output is correct
9 Correct 1293 ms 19528 KB Output is correct
10 Correct 1829 ms 21624 KB Output is correct