Skip to content

Instantly share code, notes, and snippets.

@anta0
anta0 / gist:6574318
Last active August 30, 2016 08:49
1.1つ目のSA-ISの実装
//LICENSE: CC0 (Public Domain)
#include <vector>
#include <algorithm>
class SuffixArray {
public:
typedef int Index;
//Verified: SPOJ SARRAY (0.49 / 2.8M)
template<typename AlphaT>
@anta0
anta0 / gist:6638876
Created September 20, 2013 15:02
directなRMQ的な(手抜きなのでO(n)になってないきがする)
template<typename Val, int BlockSize>
class DirectRMQ {
public:
typedef int Index; //今のところ大きくともintを仮定している(queryとか)
typedef char InBlockIndex;
typedef InBlockIndex (*BlockTypeRef)[BlockSize];
DirectRMQ() {
calcBallotNumbers();
buildInnerBlockTable();
@anta0
anta0 / RMSQ.cpp
Created September 21, 2013 13:40
Range Maximum-Sum Segment Query Problem
//LICENSE: CC0 (Public Domain)
#include <algorithm>
#include <memory>
#include <utility>
#include "../RangeMinimumQuery/DirectRMQ.cpp" //RMQを別途用意することと
//Chen, K.Y., Chao, K.M.:
//"On the Range Maximum-Sum Segment Query Problem"
//<http://www.csie.ntu.edu.tw/~kmchao/seq05fall/RMSQ.pdf>
//Tested
#include <iostream>
#include <vector>
#include <memory>
#include <limits>
#include <random>
#include <stdint.h>
#include <functional>
#include <algorithm>
//Yuan, Hao, and Mikhail J. Atallah. "Data structures for range minimum queries in multidimensional arrays." Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2010.
@anta0
anta0 / Beautiful Badges.cpp
Last active August 29, 2015 14:11
Brasil National Programming Challenge
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
// ==UserScript==
// @name SmartSubmit for AtCoder
// @version 0.200001
// @auther anta
// @description 問題閲覧画面で Ctrl+V をするだけで提出します。yukicoder <http://yukicoder.me/> の機能・コードを元にしています。
// @match http://*.contest.atcoder.jp/*
// @match https://*.contest.atcoder.jp/*
// @grant GM_getValue
// @grant GM_setValue
// @grant GM_listValues