oj.uz

Submission #990022

# Submission time Handle Problem Language Result Execution time Memory
990022 2024-05-29T11:22:55 Z HishamAlshehri Poklon (COCI17_poklon) C++17
140 / 140
 395 ms 82100 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
#define double long double
//#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")

constexpr int maxn = 500001;
constexpr int N = 1 << (int)ceil(log2(maxn));

int n, q;
int st[maxn];
int idx[maxn][3];
int a[maxn], temp[maxn], b[maxn];
vector<int>ans[maxn];
int tree[2 * N];
vector<int> range[maxn];
map<int,int>mp;

int query(int l, int r, int nl, int nr, int i) 
{
    if (nl > r || nr < l) 
        return 0;
    if (nl >= l && nr <= r) 
        return tree[i];
    int mid = (nl + nr) / 2;
    return query(l, r, nl, mid, i * 2) + query(l, r, mid + 1, nr, i * 2 + 1);
}

void update(int idx)
{
    while (idx / 2)
        {tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];idx /= 2;}
    return;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        temp[i] = a[i];
    }
    sort(temp, temp + n);
    int curr = 0;
    for (int i = 0; i < n; i++) 
    {
        if (mp[temp[i]] == NULL) 
        {
            mp[temp[i]] = curr;
            curr++;
        }
    }

    vector<int>v;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--; r--;
        v.push_back(r);
        range[r].push_back(l);
    }

    memset(idx, -1, sizeof idx);

    for (int i = 0; i < n; i++)
    {
        int state = 0;
        if (idx[a[i]][0] > -1)
            state++;
        if (idx[a[i]][1] > -1)
            state++;
        if (idx[a[i]][2] > -1)
            state++;
        if (!state)
        {
            idx[a[i]][0] = i;

            tree[i + N] = 0;

            update((i + N) / 2);
        }
        else if (state == 1)
        {
            idx[a[i]][1] = i;

            tree[idx[a[i]][1] + N] = 0;
            tree[idx[a[i]][0] + N] = 1;

            update((idx[a[i]][0] + N) / 2);
            update((idx[a[i]][1] + N) / 2);
        }
        else if (state == 2)
        {
            idx[a[i]][2] = i;

            tree[idx[a[i]][2] + N] = 0;
            tree[idx[a[i]][1] + N] = 1;
            tree[idx[a[i]][0] + N] = -1;
            update((idx[a[i]][0] + N) / 2);
            update((idx[a[i]][2] + N) / 2);
            update((idx[a[i]][1] + N) / 2);
        }
        else
        {
            tree[idx[a[i]][0] + N] = 0;
            update((idx[a[i]][0] + N) / 2);

            idx[a[i]][0] = idx[a[i]][1];
            idx[a[i]][1] = idx[a[i]][2];
            idx[a[i]][2] = i;

            tree[idx[a[i]][2] + N] = 0;
            tree[idx[a[i]][1] + N] = 1;
            tree[idx[a[i]][0] + N] = -1;

            update((idx[a[i]][0] + N) / 2);
            update((idx[a[i]][2] + N) / 2);
            update((idx[a[i]][1] + N) / 2);
        }
        for (int j : range[i])
        {
            ans[i].push_back(query(j, i, 0, N - 1, 1));
        }
    }
    for (int i = 0; i < v.size(); i++)
    {
        cout << ans[v[i]][st[v[i]]] << "\n";
        st[v[i]]++;
    }
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:60:28: warning: NULL used in arithmetic [-Wpointer-arith]
   60 |         if (mp[temp[i]] == NULL)
      |                            ^~~~
poklon.cpp:139:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47704 KB Output is correct
2 Correct 7 ms 47704 KB Output is correct
3 Correct 7 ms 47812 KB Output is correct
4 Correct 10 ms 47964 KB Output is correct
5 Correct 72 ms 54980 KB Output is correct
6 Correct 71 ms 55144 KB Output is correct
7 Correct 161 ms 62852 KB Output is correct
8 Correct 228 ms 72308 KB Output is correct
9 Correct 337 ms 77468 KB Output is correct
10 Correct 395 ms 82100 KB Output is correct