oj.uz

답안 #873635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873635 2023-11-15T12:12:10 Z sleepntsheep Poklon (COCI17_poklon) C++17
0 / 140
 279 ms 21912 KB 
#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 500000

int n, q, a[N], p[N], d[N], t[N+1], e[N];
array<int, 3> b[N];

void compress()
{
    int c[N], C = n;
    memcpy(c, a, n * sizeof *a);
    sort(c, c+C);
    for (int i = 0; i < n; ++i) a[i] = lower_bound(c, c+C, a[i]) - c;
}

void upd(int p, int k) { for (; p <= N; p+=p&-p) t[p]+=k; }
int qry(int p){ int z{0};for(;p;p-=p&-p) z+=t[p];return z;}

int main()
{
    ShinLena;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i];
    compress();
    for (int i = 0; i < q; ++i) cin >> b[i][0] >> b[i][1], b[i][2] = i;
    sort(b, b+q);
    for (int j = q - 1, i = n; i--;)
    {
        if (d[a[i]])
        {
            upd(d[a[i]]+1, 1);
            if (p[d[a[i]]]) upd(p[d[a[i]]]+1, -2);
            p[i] = d[a[i]];
        }
        for (; j >= 0 && b[j][0] == i + 1; --j) e[b[j][2]] = qry(b[j][1]);
        d[a[i]] = i;
    }
    for (int i = 0; i < q; ++i) cout << e[i] << '\n';
    return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Incorrect 2 ms 8540 KB Output isn't correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Incorrect 4 ms 8540 KB Output isn't correct
5 Incorrect 47 ms 12056 KB Output isn't correct
6 Incorrect 54 ms 12180 KB Output isn't correct
7 Incorrect 107 ms 14864 KB Output isn't correct
8 Incorrect 166 ms 17840 KB Output isn't correct
9 Incorrect 224 ms 19796 KB Output isn't correct
10 Incorrect 279 ms 21912 KB Output isn't correct