oj.uz

답안 #873638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873638 2023-11-15T12:13:51 Z sleepntsheep Poklon (COCI17_poklon) C++17
0 / 140
 278 ms 30104 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"[i+1==q];
    return 0;
}

Subtask #1
0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8536 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 52 ms 13372 KB Output isn't correct
6 Incorrect 50 ms 13660 KB Output isn't correct
7 Incorrect 109 ms 18004 KB Output isn't correct
8 Incorrect 170 ms 22828 KB Output isn't correct
9 Incorrect 236 ms 26568 KB Output isn't correct
10 Incorrect 278 ms 30104 KB Output isn't correct