Submission #989941

#	Time	Username	Problem	Language	Result	Execution time	Memory
989941		eyadooz	Poklon (COCI17_poklon)	C++14	0 / 140	260 ms	65104 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;

using namespace std;

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

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

static inline int read()
{
    int x = 0;char ch = getchar();
    while (ch < '0' || ch>'9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x;
}

static inline void print(const int &x) {
    if (x > 9)print(x / 10);
    putchar('0' + x % 10);
}

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 = read(), q = read();

    int n, q;

    cin >> n >> q;

    vector<ipair> lis[2000005];
    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]], -1);

        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