Submit Info #65845

Problem Lang User Status Time Memory
Associative Array cpp (anonymous) AC 361 ms 36.95 MiB

ケース詳細
Name Status Time Memory
2_powers_00 AC 361 ms 33.33 MiB
example_00 AC 20 ms 32.45 MiB
many_0set_00 AC 333 ms 35.16 MiB
many_0set_sparse_00 AC 115 ms 34.38 MiB
max_random_00 AC 351 ms 36.95 MiB
max_random_01 AC 360 ms 36.54 MiB
max_random_02 AC 350 ms 36.07 MiB
random_00 AC 149 ms 33.45 MiB
random_01 AC 175 ms 33.71 MiB
random_02 AC 212 ms 33.61 MiB
sparse_keys_00 AC 124 ms 35.90 MiB
sparse_keys_01 AC 143 ms 36.57 MiB
unordered_map_killer_00 AC 317 ms 33.40 MiB
unordered_map_killer_01 AC 322 ms 33.40 MiB
unordered_map_killer_02 AC 315 ms 33.38 MiB

#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_cxx; using namespace __gnu_pbds; using namespace std; template<class T, class S> ostream& operator << (ostream &o, const pair<T, S> &p) { return o << '(' << p.first << ", " << p.second << ')'; } template<template<class, class...> class T, class... A> typename enable_if<!is_same<T<A...>, string>(), ostream&>::type operator << (ostream &o, T<A...> V) { o << '['; for(auto a : V) o << a << ", "; return o << ']'; } typedef long long int ll; typedef long double ld; typedef pair<ll, ll> pl; #define G(x) ll x; cin >> x; #define GD(x) ld x; cin >> x; #define GS(s) string s; cin >> s; #define F(i, l, r) for(ll i = l; i < (r); ++i) #define FD(i, r, l) for(ll i = r; i > (l); --i) #define P(a, n) { cout << "{ "; F(_, 0, n) cout << a[_] << " "; cout << "}\n"; } #define EX(x) { cout << x << '\n'; exit(0); } #define A(a) (a).begin(), (a).end() #define K first #define V second #define M 1000000007 //998244353 //#define N 200010 struct rhash { const ll seed = __builtin_ia32_rdtsc(); ll operator()(ll x) const { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31) ^ seed; } }; template <typename T, typename U, ll C> struct cmap { rhash hsh; pair<T, U> tbl[1 << C], empt = {-1, 0}; const ll msk = (1 << C) - 1; #define I1(h) ((h) & msk) #define XR(x) I1(x >> C) void set(T t, U u) { ll h = hsh(t), i = I1(h), j = i ^ XR(h); if(tbl[i].K == t) tbl[i].V = u; else if(tbl[j].K == t) tbl[j].V = u; else while(1) { pair<T, U> v = tbl[i]; tbl[i] = {t, u}; if(v == empt) return; t = v.K, u = v.V; i ^= XR(hsh(t)); } } bool count(T t) { ll h = hsh(t), i = I1(h); return tbl[i].K == t || tbl[i ^ XR(h)].K == t; } T get(T t) { ll h = hsh(t), i = I1(h), j = i ^ XR(h); if(tbl[i].K == t) return tbl[i].V; if(tbl[j].K == t) return tbl[j].V; return empt.V; } void erase(T t) { ll h = hsh(t), i = I1(h), j = i ^ XR(h); if(tbl[i].K == t) tbl[i] = empt; else if(tbl[j].K == t) tbl[j] = empt; } void clear() { fill_n(tbl, 1 << C, empt); } }; cmap<ll, ll, 21> c; int main() { ios_base::sync_with_stdio(0); cin.tie(0); c.clear(); G(q) while(q--) { G(t) G(k) if(!t) { G(v) c.set(k, v); } else cout << c.get(k) << '\n'; } }