#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c #include template struct hashmap{ private: float load_factor = 0.8; int table_size = 16; int mod = 15; Key null_key; uint32_t mask; int valid_size; vector idx_table; vector> data; function f = std::hash(); void expand_table(){ table_size *= 2; mod = table_size - 1; idx_table.resize(table_size); fill(idx_table.begin(), idx_table.end(), -1); for(int i=0;i::max()), mask(random_device()()), valid_size(0), idx_table(table_size, -1){} int size(){ return valid_size; } void emplace(Key k, Val v){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx!=-1){ if(data[idx].first==k) return; h = (h + 1) & mod; }else{ data.push_back({k, v}); idx_table[h] = int(data.size()) - 1; valid_size++; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } void overwrite(Key k, Val v){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx!=-1){ if(data[idx].first==k){ data[idx].second = v; return; } h = (h + 1) & mod; }else{ data.push_back({k, v}); idx_table[h] = int(data.size()) - 1; valid_size++; if(float(data.size())>load_factor*float(table_size)){ expand_table(); } return; } } } void erase(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; if(idx==-1) return; if(data[idx].first==k){ data[idx].first = null_key; valid_size--; return; } h = (h + 1) & mod; } } bool contain(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ if(idx_table[h]==-1) return false; if(data[idx_table[h]].first==k) return true; h = (h + 1) & mod; } } Val at(Key k){ assert(k!=null_key); uint32_t h = f(k^mask) & mod; while(true){ int idx = idx_table[h]; assert(idx!=-1); if(data[idx].first==k) return data[idx].second; h = (h + 1) & mod; } } }; int main(){ ll n, m;scanf("%lld %lld", &n, &m); hashmap mp; for(int i=0;i