Submission #540521

#	Time	Username	Problem	Language	Result	Execution time	Memory
540521		shark25361	Poklon (COCI17_poklon)	C++14	140 / 140	894 ms	31352 KiB

poklon

#include<bits/stdc++.h>
#include <iomanip>
using namespace std;

#define FIO ios_base::sync_with_stdio(false);cin.tie(0);
#define ll int //long long
#define for_t ll T;cin>>T;while(T--)
#define endl "\n"
#define F(a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define pb push_back
#define lc(curr) (curr * 2)
#define rc(curr) ((curr * 2) + 1)

const int maxn = 500005;
ll a[maxn];
ll tree[maxn * 4];
ll arr[maxn];
ll rightv[maxn];
vector<pair<ll,pair<ll,ll>>> queries;
map<ll,ll> cnt;
map<ll,ll> occ;
//index of next occurrence of this element;

//generate array for all elements
//one by one remove elements from 0 to n
//once element is removed
//update tht index -> 0
//index of next occurrence of that element -> 0
//index of 2nd next occurrence of that element -> 1
//index of 3rd next occurrence of that element -> -1
//all other occurrences should be 0?

void build(ll curr,ll l,ll r)
{
    if(l == r)
    {
        tree[curr] = arr[l];
        return;
    }
    build(lc(curr),l,(l + r)/2);
    build(rc(curr),((l + r)/2) + 1,r);
    tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}

void update(ll curr,ll l,ll r,ll i,ll num)
{
    if(l > i || r < i)
    {
        return;
    }
    if(l == i && r == i)
    {
        tree[curr] = num;
        return;
    }
    ll mid = (l + r)/2;
    if(i <= mid)
    {
        update(lc(curr),l,mid,i,num);
    }
    else
    {
        update(rc(curr),mid + 1,r,i,num);
    }
    tree[curr] = tree[lc(curr)] + tree[rc(curr)];
}

ll query(ll curr,ll l,ll r,ll i,ll j)
{
    if(l > j || r < i)
    {
        return 0;
    }
    if(l >= i && r <= j)
    {
        return tree[curr];
    }
    ll mid = (l + r)/2;
    return query(lc(curr),l,mid,i,j) + query(rc(curr),mid + 1,r,i,j);
}

void sol()
{
    ll n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    queries.resize(q);
    for(int i = 0;i < q;i++)
    {
        cin >> queries[i].first >> queries[i].second.first;
        queries[i].second.second = i;
    }
    vector<ll> ans(q);
    memset(rightv,0,sizeof(rightv));
    memset(tree,0,sizeof(tree));
    memset(arr,0,sizeof(arr));
    sort(all(queries));
    for(int i = n;i >= 1;i--)
    {
        rightv[i] = occ[a[i]];
        occ[a[i]] = i;
    }
    for(int i = 1;i <= n;i++)
    {
        cnt[a[i]]++;
        if(cnt[a[i]] > 1)
        {
            continue;
        }
        arr[i] = 0;
        arr[rightv[i]] = 1;
        arr[rightv[rightv[i]]] = -1;
    }
    build(1,1,n);
    ll prev = 1;
    for(int i = 0;i < queries.size();i++)
    {
        ll l = queries[i].first;
        ll r = queries[i].second.first;
        ll temp;

        while(prev < l)
        {
            temp = prev;
            if(temp != 0)
            {
                arr[temp] = 0;
                update(1,1,n,temp,0);
            }

            temp = rightv[prev];
            if(temp != 0)
            {
                arr[temp] = 0;
                update(1,1,n,temp,0);
            }

            temp = rightv[rightv[prev]];
            if(temp != 0)
            {
                arr[temp] = 1;
                update(1,1,n,temp,1);
            }

            temp = rightv[rightv[rightv[prev]]];
            if(temp != 0)
            {
                arr[temp] = -1;
                update(1,1,n,temp,-1);
            }

            prev++;
        }

        arr[l] = 0;
        update(1,1,n,l,0);

        temp = rightv[l];
        if(temp != 0)
        {
            arr[temp] = 1;
            update(1,1,n,temp,1);
        }

        temp = rightv[rightv[l]];
        if(temp != 0)
        {
            arr[temp] = -1;
            update(1,1,n,temp,-1);
        }

        ans[queries[i].second.second] = query(1,1,n,l,r);
        prev = l;
    }
    for(auto it:ans)
    {
        cout << it << endl;
    }
}

int main()
{
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    FIO
    sol();
}

Compilation message (stderr)

poklon.cpp: In function 'void sol()':
poklon.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i = 0;i < queries.size();i++)
      |                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140