oj.uz

답안 #873641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873641 2023-11-15T12:19:23 Z sleepntsheep Poklon (COCI17_poklon) C++17
140 / 140
 224 ms 14932 KB 
#include <iostream>
#include <unordered_map>
#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;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")

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], t[N+1], e[N];
array<int, 3> b[N];
//int d[N];
unordered_map<int, int> d;

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);
                if (p[p[d[a[i]]]]) upd(p[p[d[a[i]]]]+1, 1);
            }
            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
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 43 ms 10844 KB Output is correct
6 Correct 42 ms 10840 KB Output is correct
7 Correct 90 ms 12184 KB Output is correct
8 Correct 137 ms 13852 KB Output is correct
9 Correct 182 ms 14420 KB Output is correct
10 Correct 224 ms 14932 KB Output is correct