oj.uz

Submission #989943

# Submission time Handle Problem Language Result Execution time Memory
989943 2024-05-29T06:51:00 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 252 ms 65112 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[200005];
//     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";
// }
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 47196 KB Output isn't correct
2 Incorrect 28 ms 47272 KB Output isn't correct
3 Incorrect 26 ms 47408 KB Output isn't correct
4 Incorrect 29 ms 47452 KB Output isn't correct
5 Incorrect 62 ms 50812 KB Output isn't correct
6 Incorrect 62 ms 50768 KB Output isn't correct
7 Incorrect 113 ms 54352 KB Output isn't correct
8 Incorrect 168 ms 58192 KB Output isn't correct
9 Incorrect 204 ms 61524 KB Output isn't correct
10 Incorrect 252 ms 65112 KB Output isn't correct