Advertisement
AlejandroGY

Untitled

Dec 28th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <algorithm>
  4. #include <cstdint>
  5.  
  6. constexpr __uint128_t MOD = 1000000000000000009ull;
  7.  
  8. void reverse(char str[], int length)
  9. {
  10.     int start = 0;
  11.     int end = length -1;
  12.     while (start < end)
  13.     {
  14.         std::swap(*(str+start), *(str+end));
  15.         start++;
  16.         end--;
  17.     }
  18. }
  19.  
  20. char* itoa(__uint128_t num, char* str, int base)
  21. {
  22.     __uint128_t i = 0;
  23.     bool isNegative = false;
  24.  
  25.     if (num == 0)
  26.     {
  27.         str[i++] = '0';
  28.         str[i] = '\0';
  29.         return str;
  30.     }
  31.  
  32.     if (num < 0 && base == 10)
  33.     {
  34.         isNegative = true;
  35.         num = -num;
  36.     }
  37.  
  38.     while (num != 0)
  39.     {
  40.         __uint128_t rem = num % base;
  41.         str[i++] = (rem > 9)? (rem-10) + 'a' : rem + '0';
  42.         num = num/base;
  43.     }
  44.  
  45.     if (isNegative)
  46.         str[i++] = '-';
  47.  
  48.     str[i] = '\0';
  49.     reverse(str, i);
  50.  
  51.     return str;
  52. }
  53.  
  54. __uint128_t sumatoria(__uint128_t x) {
  55.     __uint128_t res = (( x * (x + 1)) / 2 ) % MOD;
  56.     return res;
  57. }
  58.  
  59. int main( )
  60. {
  61.     std::ios_base::sync_with_stdio(0);
  62.     std::cin.tie(0);
  63.     std::cout.tie(0);
  64.  
  65.     uint64_t n, q, k;
  66.     std::cin >> n >> q >> k;
  67.  
  68.     __uint128_t omegas[q];
  69.     for (uint64_t i = 0; i < q; ++i) {
  70.         uint64_t l, d;
  71.         std::cin >> l >> d;
  72.         omegas[i] = ( sumatoria(__uint128_t(d)) - sumatoria(__uint128_t(l - 1)) ) % MOD;
  73.     }
  74.     std::sort(omegas, omegas + q);
  75.  
  76.     __uint128_t reyes = 0, chavos = 0, tablas = 0;
  77.     for (__uint128_t i = 0; i < k; ++i) {
  78.         uint64_t rey;
  79.         std::cin >> rey;
  80.  
  81.         auto perdidos = (omegas + q) - std::upper_bound(omegas, omegas + q, __uint128_t(rey));
  82.         auto ganados = std::lower_bound(omegas, omegas + q, __uint128_t(rey)) - omegas;
  83.         auto empates = std::upper_bound(omegas, omegas + q, __uint128_t(rey)) - std::lower_bound(omegas, omegas + q, __uint128_t(rey));
  84.         /**
  85.         std::cout << "empates:" << empates << "\n";
  86.         std::cout << "ganados:" << ganados << "\n";
  87.         std::cout << "perdidos:" << perdidos << "\n";
  88.         std::cout << "\n";
  89.         /**/
  90.  
  91.         reyes += __uint128_t(ganados);
  92.         tablas += __uint128_t(empates);
  93.         chavos += __uint128_t(perdidos);
  94.     }
  95.  
  96.     char buffer[1002];
  97.     std::cout << "Chavos :) x " << itoa(chavos, buffer, 10) << "\n";
  98.     std::cout << "Tablas :| x " << itoa(tablas, buffer, 10) << "\n";
  99.     std::cout << "Reyes :( x " << itoa(reyes, buffer, 10) << "\n";
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement