luchobazz / cpp-algorithm-snippets Goto Github PK

if(dist[e.from] + e.cost < dist[e.to] && dist[e.from] != inf)

if(dist[e.from] != inf && dist[e.from] + e.cost < dist[e.to])

const string ALPHA = "abcdefghijklmnopqrstuvwxyz";

struct RMQ {
  vector<vector<int>> table;
  RMQ(vector<int> &v) : table(20, vector<int>(v.size())) {
    int n = v.size();
    for (int i = 0; i < n; i++) table[0][i] = v[i];
    for (int j = 1; (1<<j) <= n; j++)
      for (int i = 0; i + (1<<j-1) < n; i++)
        table[j][i] = max(table[j-1][i], table[j-1][i + (1<<j-1)]);
  }
  int query(int a, int b) {
    int j = 31 - __builtin_clz(b-a+1);
    return max(table[j][a], table[j][b-(1<<j)+1]);
  }
};

// Input: 1267650600228229401496703205376
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;
const i128 ONE_128 = i128(1);
const i128 ZERO_128 = i128(0);


std::istream &operator>>(std::istream &is, i128 &n) {
    n = 0;
    std::string s;
    is >> s;
    
    for (auto c : s) {
        n = 10 * n + c - '0';
    }
    return is;
}
 
std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}


int main() {
    
    i128 number; cin >> number;
    
    for(int i = 128-1; i >= 0; i--) {
        cout << bool(number & (ONE_128 << i));
    }
    cout << endl;
    
    cout << number << endl;
    
    return 0;   
}
 

#define infinity while(1)
#define unreachable assert(false && "Unreachable");

struct SegmTree {
  vector<int> T; int n;
  SegmTree(int n) : T(2 * n, (int)-2e9), n(n) {}
  
  void Update(int pos, int val) {
    for (T[pos += n] = val; pos > 1; pos /= 2)
      T[pos / 2] = max(T[pos], T[pos ^ 1]);
  }
  
  int Query(int b, int e) {
    int res = -2e9;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) res = max(res, T[b++]);
      if (e % 2) res = max(res, T[--e]);
    }
    return res;
  }
};

auto go = y_combinator([&](auto Go, int idx) -> int64 {
    // Go(idx-1);
});

int ans = go(0);

#define _ << ' ' <<

// usage: 
cout << x _ y << endl;
// cout << x << ' ' << y << endl;

const char SPECIAL_CH = '$';
const string FIRST_ALPHA = "0";
const string SECOND_ALPHA = "1";
struct HffTreeNode {
    // One of the input characters
    char ch;
    // Frequency of the character
    uint32_t freq;
    // Left and right child
    HffTreeNode *left, *right;
    HffTreeNode(char ch, uint32_t freq) {
        left = right = NULL;
        this->ch = ch;
        this->freq = freq;
    }
};

struct Code {
    char ch;
    string bin;
};

// For comparison of
// two heap nodes (needed in min heap)
struct Compare {
    bool operator()(HffTreeNode* l, HffTreeNode* r) {
        return l->freq > r->freq;
    }
};
 
// Prints huffman codes from
// the root of Huffman Tree.
void buildCodes(vector<Code> &codes, struct HffTreeNode* root, string str) {
    if (!root) return;
    if (root->ch != SPECIAL_CH) codes.push_back(Code{root->ch, str});
    buildCodes(codes, root->left, str + FIRST_ALPHA);
    buildCodes(codes, root->right, str + SECOND_ALPHA);
}
 
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
HffTreeNode* HuffmanCodes(vector<char> alpha, vector<int> freq) {
    int size = (int) alpha.size();
    struct HffTreeNode *left, *right, *top;
    // Create a min heap & inserts all characters of alpha[]
    priority_queue<HffTreeNode*, vector<HffTreeNode*>, Compare> minHeap;
    
    for (int i = 0; i < size; ++i) {
        minHeap.push(new HffTreeNode(alpha[i], freq[i]));
    }
    #define pop_heap(heap) heap.top(); heap.pop();
    
    // Iterate while size of heap doesn't become 1
    while (minHeap.size() != 1) {
        // Extract the two minimum
        // freq items from min heap
        left = pop_heap(minHeap);
        right = pop_heap(minHeap);
        // Create a new internal node with frequency equal to the sum of the
        // two nodes frequencies. Make the two extracted node as left and right
        // children of this new node. Add this node to the min heap '$'
        // is a special value for internal nodes, not used
        top = new HffTreeNode(SPECIAL_CH, left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    return minHeap.top();
}

// Usage:
// vector<char> alpha = { 'a', 'b', 'c', 'd', 'e', 'f' };
// vector<int> freq = { 5, 9, 12, 13, 16, 45 };
// HffTreeNode* root = HuffmanCodes(alpha, freq);
// vector<Code> codes;
// buildCodes(codes, root, "");
// for(auto &code: codes) cout << code.ch << ": " << code.bin << endl;

PrefixSum() n(-1) {}

PrefixSum(): n(-1) {}

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")