Submission #539865

# Submission time Handle Problem Language Result Execution time Memory
539865 2022-03-19T07:46:44 Z shark25361 Poklon (COCI17_poklon) C++14
0 / 140
620 ms 524288 KB
#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,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 == r)
    {
        tree[curr] = num;
        return;
    }
    update(lc(curr),l,(l + r)/2,i,num);
    update(rc(curr),((l + r)/2),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];
    }
    return query(lc(curr),l,(l + r)/2,i,j) + query(rc(curr),((l + r)/2) + 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;
    }
    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--)
    {
        if(occ[a[i]] > 0)
        {
            rightv[i] = occ[a[i]];
        }
        else
        {
            rightv[i] = 0;
        }
        occ[a[i]] = i;
    }
    for(int i = 1;i <= n;i++)
    {
        cnt[a[i]]++;
        if(cnt[a[i]] > 1)
        {
            continue;
        }
        bool temp = false;
        if(rightv[i] != inf)
        {
            arr[i] = 0;
            arr[rightv[i]] = 1;
            if(rightv[rightv[i]] != inf)
            {
                arr[rightv[rightv[i]]] = -1;
            }
        }
    }
    build(1,1,n);
    for(int i = 0;i < queries.size();i++)
    {
        ll l = queries[i].first;
        ll r = queries[i].second;
        if(i && queries[i].first != queries[i - 1].first)//have to update for new values
        {
            if(rightv[l] != inf)
            {
                update(1,1,n,l,0);
                update(1,1,n,rightv[l],1);
                if(rightv[rightv[l]] != inf)
                {
                   update(1,1,n,rightv[rightv[l]],-1);
                }
            }
        }
        cout << query(1,1,n,l,r) << endl;
    }
}

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

Compilation message

poklon.cpp: In function 'void sol()':
poklon.cpp:113:14: warning: unused variable 'temp' [-Wunused-variable]
  113 |         bool temp = false;
      |              ^~~~
poklon.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i = 0;i < queries.size();i++)
      |                   ~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 343 ms 524288 KB Execution killed with signal 9
2 Runtime error 300 ms 524288 KB Execution killed with signal 9
3 Runtime error 310 ms 524288 KB Execution killed with signal 9
4 Runtime error 250 ms 524288 KB Execution killed with signal 9
5 Runtime error 344 ms 524288 KB Execution killed with signal 9
6 Runtime error 349 ms 524288 KB Execution killed with signal 9
7 Runtime error 390 ms 524288 KB Execution killed with signal 9
8 Runtime error 429 ms 524288 KB Execution killed with signal 9
9 Runtime error 493 ms 524288 KB Execution killed with signal 9
10 Runtime error 620 ms 524288 KB Execution killed with signal 9