Submission #989945

#	Time	Username	Problem	Language	Result	Execution time	Memory
989945		eyadooz	Poklon (COCI17_poklon)	C++14	0 / 140	265 ms	31616 KiB

poklon

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <math.h>
#include <array>
#include <random>
#include <bitset>
#include <climits>
#include <cstring>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template <class x>
// using ordered_set = tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>;

typedef pair<int, int> ipair;

#define endl '\n'
#define mod 1000000007
#define INF 0x3f3f3f3f

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

struct BIT
{
    int size;
    vector<int> bit;
    BIT(int n) : size(n), bit(n + 1) {}
    void update(int x, int y)
    {
        x++;
        for(;x <= size;x += (x & (-x)))
            bit[x] += y;
    }

    int query(int x)
    {
        x++;
        int ans = 0;
        for(;x > 0;x -= (x & (-x))) ans += bit[x];
        return ans;
    }
};

int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, q;

    cin >> n >> q;

    vector<ipair> lis[n];
    int list[n];
    for(int i = 0;i < n;cin >> list[i++]);

    for(int i = 0;i < q;i++)
    {
        int x, y;

        cin >> x >> y;
        x--, y--;

        lis[x].push_back({y, i});
    }

    BIT bit(n);

    map<int, int> asd;
    vector<int> ans(q, -1);

    for(int i = n-1;i >= 0;i--)
    {
        if(asd.count(list[i])) bit.update(asd[list[i]], -2);

        asd[list[i]] = i;
        bit.update(i, 1);

        for(auto j : lis[i])
        {
            ans[j.second] = bit.query(j.first);
        }
    }

    for(auto i : ans) cout << i << "\n";
}

• Subtask 1: 0 / 140