제출 #873641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873641		sleepntsheep	Poklon (COCI17_poklon)	C++17	140 / 140	224 ms	14932 KiB

poklon

#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 / 140