Cod sursa(job #2654003)

Utilizator PetyAlexandru Peticaru Pety Data 29 septembrie 2020 17:34:11
Problema Nums Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser fin ("nums.in");
ofstream fout ("nums.out");

int n, m,k, aib[100002];
string v[100002], s[100002];
int q[100002], viz[100002], nr[100002];

void update (int x) {
  for (int i = x; i <= m; i += (i & -i))
    aib[i]++;
}

int query (int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
    s += aib[i];
  return s;
}
bool cmp (string a, string b) {
  if (a.size() != b.size())
    return a.size() < b.size();
  else
    return a < b;
}

int main()
{
  fin >> n;
  m = 0;
  for (int i = 1; i <= n; i++) {
    int t;
    fin >> t;
    q[i] = t;
    if (t) {
      fin >> v[i];
      s[++m] = v[i];
    }
    else
      fin >> nr[i];
  }
  sort(s + 1,s + m + 1, cmp);
  int m1 = 0;
  unordered_map<string, int>mp;
  for (int i = 1; i <= m; i++)
    if (i == 1 || s[i] != s[i - 1]) {
      s[++m1] = s[i];
      mp[s[i]] = m1;
    }
  m = m1;
  for (int i = 1; i <= n; i++) {
    if (q[i]) {
      int poz = mp[v[i]];
      if (!viz[poz])
        update(poz);
      viz[poz] = 1;
    }
    else {
      int sum = 0, sol = 0;
      for (int j = (1 << 16); j; j >>= 1)
        if (sol + j <= m && sum + aib[sol + j] < nr[i]) {
          sol += j;
          sum += aib[sol];
        }
      fout << s[sol + 1] << "\n";
    }
  }
  return 0;
}