Artifact 7a3d2ba79608ced5b9c0509c333c9183c04a939f:
0000: 2f 2f 0a 2f 2f 20 61 63 63 75 6d 75 6c 61 74 69 //.// accumulati
0010: 76 65 20 6d 61 70 0a 2f 2f 20 20 20 62 61 73 69 ve map.// basi
0020: 63 61 6c 6c 79 20 61 20 6d 61 70 3c 4b 2c 56 3e cally a map<K,V>
0030: 2c 20 62 75 74 20 69 74 20 65 6c 69 6d 69 6e 61 , but it elimina
0040: 74 65 73 20 64 75 70 6c 69 63 61 74 69 6f 6e 20 tes duplication
0050: 6c 61 7a 69 6c 79 0a 2f 2f 20 20 20 66 69 72 73 lazily.// firs
0060: 74 20 6b 65 65 70 20 61 6c 6c 20 69 6e 73 65 72 t keep all inser
0070: 74 65 64 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 ted elements in
0080: 61 20 76 65 63 74 6f 72 2e 20 6f 6e 6c 79 20 77 a vector. only w
0090: 68 65 6e 20 74 68 65 20 62 75 66 66 65 72 0a 2f hen the buffer./
00a0: 2f 20 20 20 6f 76 65 72 66 6c 6f 77 73 2c 20 69 / overflows, i
00b0: 74 20 65 6c 69 6d 69 6e 61 74 65 73 20 64 75 70 t eliminates dup
00c0: 6c 69 63 61 74 69 6f 6e 0a 2f 2f 0a 0a 74 65 6d lication.//..tem
00d0: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 4b plate<typename K
00e0: 2c 20 74 79 70 65 6e 61 6d 65 20 56 2c 20 69 6e , typename V, in
00f0: 74 20 4c 49 4d 49 54 20 3d 20 28 31 3c 3c 32 36 t LIMIT = (1<<26
0100: 29 2f 33 2f 73 69 7a 65 6f 66 28 70 61 69 72 3c )/3/sizeof(pair<
0110: 4b 2c 56 3e 29 3e 0a 73 74 72 75 63 74 20 61 6d K,V>)>.struct am
0120: 61 70 0a 7b 0a 09 74 79 70 65 64 65 66 20 74 79 ap.{..typedef ty
0130: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 20 70 pename vector< p
0140: 61 69 72 3c 4b 2c 56 3e 20 3e 3a 3a 69 74 65 72 air<K,V> >::iter
0150: 61 74 6f 72 20 69 74 65 72 61 74 6f 72 3b 0a 09 ator iterator;..
0160: 73 74 72 75 63 74 20 42 79 4b 65 79 20 7b 20 62 struct ByKey { b
0170: 6f 6f 6c 20 6f 70 65 72 61 74 6f 72 28 29 28 63 ool operator()(c
0180: 6f 6e 73 74 20 70 61 69 72 3c 4b 2c 56 3e 26 20 onst pair<K,V>&
0190: 61 2c 20 63 6f 6e 73 74 20 70 61 69 72 3c 4b 2c a, const pair<K,
01a0: 56 3e 26 20 62 29 20 63 6f 6e 73 74 20 7b 20 72 V>& b) const { r
01b0: 65 74 75 72 6e 20 61 2e 66 69 72 73 74 3c 62 2e eturn a.first<b.
01c0: 66 69 72 73 74 3b 20 7d 20 7d 3b 0a 0a 09 76 65 first; } };...ve
01d0: 63 74 6f 72 3c 20 70 61 69 72 3c 4b 2c 56 3e 20 ctor< pair<K,V>
01e0: 3e 20 6b 76 3b 0a 09 61 6d 61 70 28 29 20 7b 20 > kv;..amap() {
01f0: 6b 76 2e 72 65 73 65 72 76 65 28 4c 49 4d 49 54 kv.reserve(LIMIT
0200: 29 3b 20 7d 0a 0a 09 76 6f 69 64 20 61 64 64 28 ); }...void add(
0210: 63 6f 6e 73 74 20 4b 26 20 6b 2c 20 63 6f 6e 73 const K& k, cons
0220: 74 20 56 26 20 76 29 0a 09 7b 0a 09 09 6b 76 2e t V& v)..{...kv.
0230: 70 75 73 68 5f 62 61 63 6b 28 20 6d 61 6b 65 5f push_back( make_
0240: 70 61 69 72 28 6b 2c 76 29 20 29 3b 0a 09 09 69 pair(k,v) );...i
0250: 66 28 20 6b 76 2e 73 69 7a 65 28 29 20 3d 3d 20 f( kv.size() ==
0260: 4c 49 4d 49 54 20 29 0a 09 09 09 6e 6f 72 6d 61 LIMIT )....norma
0270: 6c 69 7a 65 28 29 3b 0a 09 7d 0a 0a 09 69 74 65 lize();..}...ite
0280: 72 61 74 6f 72 20 62 65 67 69 6e 28 29 20 20 20 rator begin()
0290: 20 20 20 20 7b 20 72 65 74 75 72 6e 20 6b 76 2e { return kv.
02a0: 62 65 67 69 6e 28 29 3b 20 7d 0a 09 69 74 65 72 begin(); }..iter
02b0: 61 74 6f 72 20 65 6e 64 28 29 20 20 20 20 20 20 ator end()
02c0: 20 20 20 7b 20 72 65 74 75 72 6e 20 6b 76 2e 65 { return kv.e
02d0: 6e 64 28 29 3b 20 7d 0a 09 76 6f 69 64 20 73 77 nd(); }..void sw
02e0: 61 70 28 20 61 6d 61 70 26 20 72 68 73 20 29 20 ap( amap& rhs )
02f0: 7b 20 6b 76 2e 73 77 61 70 28 72 68 73 2e 6b 76 { kv.swap(rhs.kv
0300: 29 3b 20 7d 0a 0a 09 2f 2f 20 54 65 73 74 65 64 ); }...// Tested
0310: 3a 20 53 52 4d 20 34 36 39 20 4c 76 33 20 28 41 : SRM 469 Lv3 (A
0320: 63 63 75 6d 75 6c 61 74 65 29 0a 09 76 6f 69 64 ccumulate)..void
0330: 20 6e 6f 72 6d 61 6c 69 7a 65 28 29 0a 09 7b 0a normalize()..{.
0340: 09 09 73 6f 72 74 28 6b 76 2e 62 65 67 69 6e 28 ..sort(kv.begin(
0350: 29 2c 20 6b 76 2e 65 6e 64 28 29 2c 20 42 79 4b ), kv.end(), ByK
0360: 65 79 28 29 29 3b 0a 09 09 69 6e 74 20 69 3d 30 ey());...int i=0
0370: 3b 0a 09 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b ;...for(int j=0;
0380: 20 6a 3c 6b 76 2e 73 69 7a 65 28 29 3b 20 2b 2b j<kv.size(); ++
0390: 69 29 0a 09 09 7b 0a 09 09 09 69 6e 74 20 6b 20 i)...{....int k
03a0: 3d 20 6a 3b 0a 09 09 09 6b 76 5b 69 5d 20 3d 20 = j;....kv[i] =
03b0: 6b 76 5b 6b 5d 3b 0a 09 09 09 77 68 69 6c 65 28 kv[k];....while(
03c0: 20 2b 2b 6a 3c 6b 76 2e 73 69 7a 65 28 29 20 26 ++j<kv.size() &
03d0: 26 20 6b 76 5b 6b 5d 2e 66 69 72 73 74 3d 3d 6b & kv[k].first==k
03e0: 76 5b 6a 5d 2e 66 69 72 73 74 20 29 0a 09 09 09 v[j].first )....
03f0: 09 6b 76 5b 69 5d 2e 73 65 63 6f 6e 64 20 2b 3d .kv[i].second +=
0400: 20 6b 76 5b 6a 5d 2e 73 65 63 6f 6e 64 3b 0a 09 kv[j].second;..
0410: 09 7d 0a 09 09 6b 76 2e 72 65 73 69 7a 65 28 69 .}...kv.resize(i
0420: 29 3b 0a 09 7d 0a 2f 2a 0a 09 2f 2f 20 4e 6f 74 );..}./*..// Not
0430: 20 54 65 73 74 65 64 20 28 50 72 65 66 65 72 20 Tested (Prefer
0440: 46 69 72 73 74 29 0a 09 76 6f 69 64 20 6e 6f 72 First)..void nor
0450: 6d 61 6c 69 7a 65 28 29 0a 09 7b 0a 09 09 73 6f malize()..{...so
0460: 72 74 28 6b 76 2e 62 65 67 69 6e 28 29 2c 20 6b rt(kv.begin(), k
0470: 76 2e 65 6e 64 28 29 2c 20 42 79 4b 65 79 28 29 v.end(), ByKey()
0480: 29 3b 0a 09 09 69 6e 74 20 69 3d 30 3b 0a 09 09 );...int i=0;...
0490: 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6b for(int j=0; j<k
04a0: 76 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 v.size(); ++i)..
04b0: 09 7b 0a 09 09 09 69 6e 74 20 6b 20 3d 20 6a 3b .{....int k = j;
04c0: 0a 09 09 09 6b 76 5b 69 5d 20 3d 20 6b 76 5b 6b ....kv[i] = kv[k
04d0: 5d 3b 0a 09 09 09 77 68 69 6c 65 28 20 2b 2b 6a ];....while( ++j
04e0: 3c 6b 76 2e 73 69 7a 65 28 29 20 26 26 20 6b 76 <kv.size() && kv
04f0: 5b 6b 5d 2e 66 69 72 73 74 3d 3d 6b 76 5b 6a 5d [k].first==kv[j]
0500: 2e 66 69 72 73 74 20 29 0a 09 09 09 09 7b 7d 0a .first ).....{}.
0510: 09 09 7d 0a 09 09 6b 76 2e 72 65 73 69 7a 65 28 ..}...kv.resize(
0520: 69 29 3b 0a 09 7d 0a 0a 09 2f 2f 20 4e 6f 74 20 i);..}...// Not
0530: 54 65 73 74 65 64 20 28 50 72 65 66 65 72 20 4c Tested (Prefer L
0540: 61 73 74 29 0a 09 76 6f 69 64 20 6e 6f 72 6d 61 ast)..void norma
0550: 6c 69 7a 65 28 29 0a 09 7b 0a 09 09 73 6f 72 74 lize()..{...sort
0560: 28 6b 76 2e 62 65 67 69 6e 28 29 2c 20 6b 76 2e (kv.begin(), kv.
0570: 65 6e 64 28 29 2c 20 42 79 4b 65 79 28 29 29 3b end(), ByKey());
0580: 0a 09 09 69 6e 74 20 69 3d 30 3b 0a 09 09 66 6f ...int i=0;...fo
0590: 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 6b 76 2e r(int j=0; j<kv.
05a0: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 09 7b size(); ++i)...{
05b0: 0a 09 09 09 69 6e 74 20 6b 20 3d 20 6a 3b 0a 09 ....int k = j;..
05c0: 09 09 77 68 69 6c 65 28 20 2b 2b 6a 3c 6b 76 2e ..while( ++j<kv.
05d0: 73 69 7a 65 28 29 20 26 26 20 6b 76 5b 6b 5d 2e size() && kv[k].
05e0: 66 69 72 73 74 3d 3d 6b 76 5b 6a 5d 2e 66 69 72 first==kv[j].fir
05f0: 73 74 20 29 0a 09 09 09 09 7b 7d 0a 09 09 09 6b st ).....{}....k
0600: 76 5b 69 5d 20 3d 20 6b 76 5b 6a 2d 31 5d 3b 0a v[i] = kv[j-1];.
0610: 09 09 7d 0a 09 09 6b 76 2e 72 65 73 69 7a 65 28 ..}...kv.resize(
0620: 69 29 3b 0a 09 7d 0a 2a 2f 0a 7d 3b 0a i);..}.*/.};.