oj.uz

Submission #989945

# Submission time Handle Problem Language Result Execution time Memory
989945 2024-05-29T06:56:48 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 265 ms 31616 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 2 ms 604 KB Output isn't correct
5 Incorrect 37 ms 6480 KB Output isn't correct
6 Incorrect 38 ms 6472 KB Output isn't correct
7 Incorrect 88 ms 12884 KB Output isn't correct
8 Incorrect 160 ms 18984 KB Output isn't correct
9 Incorrect 188 ms 25420 KB Output isn't correct
10 Incorrect 265 ms 31616 KB Output isn't correct