oj.uz

답안 #989942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989942 2024-05-29T06:48:16 Z eyadooz Poklon (COCI17_poklon) C++14
0 / 140
 88 ms 14012 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;

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[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";
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Incorrect 3 ms 5148 KB Output isn't correct
3 Incorrect 3 ms 4956 KB Output isn't correct
4 Incorrect 4 ms 5212 KB Output isn't correct
5 Incorrect 37 ms 8488 KB Output isn't correct
6 Incorrect 37 ms 8528 KB Output isn't correct
7 Incorrect 88 ms 12112 KB Output isn't correct
8 Runtime error 19 ms 12376 KB Execution killed with signal 11
9 Runtime error 23 ms 13104 KB Execution killed with signal 11
10 Runtime error 27 ms 14012 KB Execution killed with signal 11