Cod sursa(job #2647317)

Utilizator CONFUSION@@@@@ @@@ CONFUSION Data 3 septembrie 2020 21:21:38
Problema Secventa 5 Scor 90
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.89 kb
#include <bits/stdc++.h>
#define BUFSIZE 0x20000
using namespace std;

int rpos;
char rbuf[BUFSIZE], cf[9];
static inline char readChar() {
  if (!(rpos = (rpos+1) & (BUFSIZE-1)))
    fread(rbuf, 1, BUFSIZE, stdin);
  return rbuf[rpos];
}

static inline int readInt() {
  int ch;
  int ret = 0;
  while (!isdigit(ch = readChar()));

  do
    ret = (ret << 3) + (ret << 1) + ch - '0';
  while (isdigit(ch = readChar()));

  return ret;
}

struct custom_hash {
    static uint64_t splitmix64 (uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator () (uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map <int, int, custom_hash> Hash;
unordered_map <int, int, custom_hash> sex;

int v[(1 << 20) + 1], n, l, u;
unsigned long long go1 (int x) {
    unsigned long long ans = 0;

    int poz = 1, it;
    for (it = 1; it <= n; it++) {
        ++Hash[v[it]];
        while (Hash.size() > x) {
            if (--Hash[v[poz]] == 0)
                Hash.erase(v[poz]);
            poz++;
        }
        
        ans += it - poz + 1;
    }

    return ans;
}

unsigned long long go2 (int x) {
    unsigned long long ans = 0;

    int poz = 1, it;
    for (it = 1; it <= n; it++) {
        ++sex[v[it]];
        while (sex.size() > x) {
            if (--sex[v[poz]] == 0)
                sex.erase(v[poz]);
            poz++;
        }
        
        ans += it - poz + 1;
    }

    return ans;
}


int main () {
    freopen("secv5.in", "r", stdin);
    ofstream fout ("secv5.out");

    n = readInt(), l = readInt(), u = readInt();
    
    int i;
    for (i = 1; i <= n; i++)
        v[i] = readInt();

    fout << go1(u) - go2(l - 1);
    return 0;
}