-
Notifications
You must be signed in to change notification settings - Fork 0
/
legacywithsetfastsetvector.cpp
134 lines (129 loc) · 5.89 KB
/
legacywithsetfastsetvector.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a) begin(a),end(a)
#define FOR(x,val,to) for(int x=(val);x<int((to));++x)
#define FORE(x,val,to) for(auto x=(val);x<=(to);++x)
#define FORR(x,arr) for(auto &x: arr)
#define FORS(x,plus,arr) for(auto x = begin(arr)+(plus); x != end(arr); ++x)
#define FORREV(x,plus,arr) for(auto x = (arr).rbegin()+(plus); x !=(arr).rend(); ++x)
#define REE(s_) {cout<<s_<<'\n';exit(0);}
#define GET(arr) for(auto &i: (arr)) sc(i)
#define whatis(x) cerr << #x << " is " << (x) << endl;
#define e1 first
#define e2 second
#define INF 0x7f7f7f7f
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::string> vs;
typedef int64_t ll;
typedef uint64_t ull;
#define umap unordered_map
#define uset unordered_set
using namespace std;
using namespace __gnu_pbds;
#ifdef ONLINE_JUDGE
#define whatis(x) ;
#endif
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
template<class L, class R> ostream& operator<<(ostream &os, map<L, R> P) { for(auto const &vv: P)os<<"("<<vv.first<<","<<vv.second<<")"; return os; }
template<class T> ostream& operator<<(ostream &os, set<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os<<"[";for(auto const &vv:V)os<<vv<<","; os<<"]"; return os; }
template<class L, class R> ostream& operator<<(ostream &os, pair<L, R> P) { os<<"("<<P.first<<","<<P.second<<")"; return os; }
inline int fstoi(const string &str){auto it=str.begin();bool neg=0;int num=0;if(*it=='-')neg=1;else num=*it-'0';++it;while(it<str.end()) num=num*10+(*it++-'0');if(neg)num*=-1;return num;}
inline void getch(char &x){while(x = getchar_unlocked(), x < 33){;}}
inline void getstr(string &str){str.clear(); char cur;while(cur=getchar_unlocked(),cur<33){;}while(cur>32){str+=cur;cur=getchar_unlocked();}}
template<typename T> inline bool sc(T &num){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){if(c == EOF) return false;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; return true;}template<typename T, typename ...Args> inline void sc(T &num, Args &...args){ bool neg=0; int c; num=0; while(c=getchar_unlocked(),c<33){;} if(c=='-'){ neg=1; c=getchar_unlocked(); } for(;c>47;c=getchar_unlocked()) num=num*10+c-48; if(neg) num*=-1; sc(args...); }
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //s.find_by_order(), s.order_of_key() <- works like lower_bound
template<typename T> using ordered_map = tree<T, int, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/* #define N 10001 */
/* #define N 100001 */
#define N 1000001
// potrzebuję własny iterator also pod ++, --.
template<typename T>
class fastset {
public:
T lower_bound(const T &key) {
auto it1 = ::lower_bound(large.begin(), large.end(), key);
auto it2 = small.lower_bound(key);
/* auto it2 = ::lower_bound(small.begin(), small.end(), key); */
return it1 != large.end() && (it2 == small.end() || *it1 <= *it2) ? *it1 : it2 == small.end() ? INF : *it2;
}
bool insert(const T &val){
auto it = ::lower_bound(large.begin(), large.end(), val);
if (it != large.end() && *it == val)
return 0;
bool inserted = small.insert(val).second;
if (!inserted)
return 0;
/* auto it2 = ::lower_bound(small.begin(), small.end(), val); */
/* if (it2 != small.end() && *it2 == val) */
/* return 0; */
/* small.insert(it2, val); */
if (small.size() >= small_bound) {
int origlgsz = large.size();
int newn = large.size() + small.size();
large.resize(newn);
// Reverse iterator can be slower.
auto it1 = small.end();
auto it2 = large.begin() + origlgsz;
for (int i = newn - 1; i >= 0; --i) {
if (it2 != large.begin() && (it1 == small.begin() || *prev(it2) >= *prev(it1))){
large[i] = *--it2;
}
else{
large[i] = *--it1;
}
}
small.clear();
}
return 1;
}
ssize_t size() const {
return large.size() + small.size();
}
bool empty() const {
return !size();
}
void clear() {
small.clear();
large.clear();
}
private:
/* static constexpr int small_bound = 50000; */
static constexpr int small_bound = 30000;
/* static constexpr int small_bound = 1024; */
/* static constexpr int small_bound = 4096; */
// giga taktyk -> trzymanie unsorted części vectora również w large (na
// końcu); wtedy lepszy cacheeff, i np. można inplace_merge użyć.
// inplace_merge does try to get_temporary_buffer though.
// -> wtedy tylko mały bound mógłby być. let's try.
// -> 0.021s z 1024bnd, better than std::set, pog. Chyba to jest meta.
vector<T> large;
set<T> small;
/* vector<T> small; */
};
// 0.023 std::set vs 0.275s fastset setbnd64 1e5 inserts + 2 lower_bounds -> terrible.
// Im mniejszy small_bound tym gorzej. W sumie rzeczywiście znacznie za mały wziąłem, powinien być pokroju tego sqrt.
// 1024 -> 0.038
// 8024 -> 0.028
// 20k, 30l -> 0.03s
// 1M inserts std::set 0.533s ; 0.509s 1024bnd2xvec | 0.332s 4096; | 10096 0.369s; | 0.332 5096 | 0.377s 2048
// 1M z vecxsetem dla 30000 0.487s najlepiej.
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
fastset<int> st;
/* set<int> st; */
int a[N];
iota(a,a+N,0);
random_shuffle(a,a+N);
FORR(i,a)
st.insert(i);
cout << st.lower_bound(-4) << ' ' << st.lower_bound(2137) << '\n';
/* cout << *st.lower_bound(-4) << ' ' << *st.lower_bound(2137) << '\n'; */
}