0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 4d 69 6e 69 P;....class Mini
01a0: 6e 67 47 6f 6c 64 48 61 72 64 20 7b 20 70 75 62 ngGoldHard { pub
01b0: 6c 69 63 3a 0d 0a 09 69 6e 74 20 47 65 74 4d 61 lic:...int GetMa
01c0: 78 69 6d 75 6d 47 6f 6c 64 28 69 6e 74 20 4e 2c ximumGold(int N,
01d0: 20 69 6e 74 20 4d 2c 20 76 65 63 74 6f 72 20 3c int M, vector <
01e0: 69 6e 74 3e 20 65 76 65 6e 74 5f 69 2c 20 76 65 int> event_i, ve
01f0: 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 ctor <int> event
0200: 5f 6a 2c 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e _j, vector <int>
0210: 20 65 76 65 6e 74 5f 64 69 2c 20 76 65 63 74 6f event_di, vecto
0220: 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 64 6a r <int> event_dj
0230: 29 0d 0a 09 7b 0d 0a 09 09 72 65 74 75 72 6e 20 )...{....return
0240: 73 6f 6c 76 65 28 4e 2c 20 65 76 65 6e 74 5f 69 solve(N, event_i
0250: 2c 20 65 76 65 6e 74 5f 64 69 29 20 2b 20 73 6f , event_di) + so
0260: 6c 76 65 28 4d 2c 20 65 76 65 6e 74 5f 6a 2c 20 lve(M, event_j,
0270: 65 76 65 6e 74 5f 64 6a 29 3b 0d 0a 09 7d 0d 0a event_dj);...}..
0280: 0d 0a 09 69 6e 74 20 73 6f 6c 76 65 28 69 6e 74 ...int solve(int
0290: 20 57 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 W, const vector
02a0: 3c 69 6e 74 3e 26 20 65 2c 20 63 6f 6e 73 74 20 <int>& e, const
02b0: 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 64 29 0d vector<int>& d).
02c0: 0a 09 7b 0d 0a 09 09 76 65 63 74 6f 72 3c 69 6e ..{....vector<in
02d0: 74 3e 20 64 70 28 57 2b 31 2c 20 30 29 3b 0d 0a t> dp(W+1, 0);..
02e0: 09 09 66 6f 72 28 69 6e 74 20 78 3d 30 3b 20 78 ..for(int x=0; x
02f0: 3c 3d 57 3b 20 2b 2b 78 29 0d 0a 09 09 09 64 70 <=W; ++x).....dp
0300: 5b 78 5d 20 3d 20 57 20 2d 20 61 62 73 28 78 2d [x] = W - abs(x-
0310: 65 5b 30 5d 29 3b 0d 0a 0d 0a 09 09 66 6f 72 28 e[0]);......for(
0320: 69 6e 74 20 69 3d 30 3b 20 69 3c 64 2e 73 69 7a int i=0; i<d.siz
0330: 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 e(); ++i) {.....
0340: 76 65 63 74 6f 72 3c 69 6e 74 3e 20 64 70 32 28 vector<int> dp2(
0350: 57 2b 31 2c 20 30 29 3b 0d 0a 09 09 09 66 6f 72 W+1, 0);.....for
0360: 28 69 6e 74 20 78 3d 30 3b 20 78 3c 3d 57 3b 20 (int x=0; x<=W;
0370: 2b 2b 78 29 0d 0a 09 09 09 09 64 70 32 5b 78 5d ++x)......dp2[x]
0380: 20 3d 20 57 20 2d 20 61 62 73 28 78 2d 65 5b 69 = W - abs(x-e[i
0390: 2b 31 5d 29 3b 0d 0a 0d 0a 09 09 09 64 65 71 75 +1]);.......dequ
03a0: 65 3c 69 6e 74 3e 20 71 3b 0d 0a 09 09 09 69 6e e<int> q;.....in
03b0: 74 20 70 78 20 3d 20 30 3b 0d 0a 09 09 09 66 6f t px = 0;.....fo
03c0: 72 28 70 78 3d 30 3b 20 70 78 3c 3d 64 5b 69 5d r(px=0; px<=d[i]
03d0: 20 26 26 20 70 78 3c 3d 57 3b 20 2b 2b 70 78 29 && px<=W; ++px)
03e0: 20 7b 0d 0a 09 09 09 09 77 68 69 6c 65 28 21 71 {......while(!q
03f0: 2e 65 6d 70 74 79 28 29 20 26 26 20 64 70 5b 71 .empty() && dp[q
0400: 2e 62 61 63 6b 28 29 5d 20 3c 20 64 70 5b 70 78 .back()] < dp[px
0410: 5d 29 0d 0a 09 09 09 09 09 71 2e 70 6f 70 5f 62 ]).......q.pop_b
0420: 61 63 6b 28 29 3b 0d 0a 09 09 09 09 71 2e 70 75 ack();......q.pu
0430: 73 68 5f 62 61 63 6b 28 70 78 29 3b 0d 0a 09 09 sh_back(px);....
0440: 09 7d 0d 0a 0d 0a 09 09 09 66 6f 72 28 69 6e 74 .}.......for(int
0450: 20 78 3d 30 3b 20 78 3c 3d 57 3b 20 2b 2b 78 29 x=0; x<=W; ++x)
0460: 20 7b 0d 0a 09 09 09 09 77 68 69 6c 65 28 71 2e {......while(q.
0470: 66 72 6f 6e 74 28 29 20 3c 20 78 2d 64 5b 69 5d front() < x-d[i]
0480: 29 0d 0a 09 09 09 09 09 71 2e 70 6f 70 5f 66 72 ).......q.pop_fr
0490: 6f 6e 74 28 29 3b 0d 0a 0d 0a 09 09 09 09 64 70 ont();........dp
04a0: 32 5b 78 5d 20 2b 3d 20 64 70 5b 71 2e 66 72 6f 2[x] += dp[q.fro
04b0: 6e 74 28 29 5d 3b 0d 0a 0d 0a 09 09 09 09 69 66 nt()];........if
04c0: 28 70 78 3c 3d 57 29 20 7b 0d 0a 09 09 09 09 09 (px<=W) {.......
04d0: 77 68 69 6c 65 28 21 71 2e 65 6d 70 74 79 28 29 while(!q.empty()
04e0: 20 26 26 20 64 70 5b 71 2e 62 61 63 6b 28 29 5d && dp[q.back()]
04f0: 20 3c 20 64 70 5b 70 78 5d 29 0d 0a 09 09 09 09 < dp[px])......
0500: 09 09 71 2e 70 6f 70 5f 62 61 63 6b 28 29 3b 0d ..q.pop_back();.
0510: 0a 09 09 09 09 09 71 2e 70 75 73 68 5f 62 61 63 ......q.push_bac
0520: 6b 28 70 78 29 3b 0d 0a 0d 0a 09 09 09 09 09 2b k(px);.........+
0530: 2b 70 78 3b 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 +px;......}.....
0540: 7d 0d 0a 0d 0a 09 09 09 64 70 2e 73 77 61 70 28 }.......dp.swap(
0550: 64 70 32 29 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 dp2);....}....re
0560: 74 75 72 6e 20 2a 6d 61 78 5f 65 6c 65 6d 65 6e turn *max_elemen
0570: 74 28 64 70 2e 62 65 67 69 6e 28 29 2c 20 64 70 t(dp.begin(), dp
0580: 2e 65 6e 64 28 29 29 3b 0d 0a 09 7d 0d 0a 7d 3b .end());...}..};
0590: 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 ....// BEGIN CUT
05a0: 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 HERE..#include
05b0: 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 <ctime>..double
05c0: 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 start_time; stri
05d0: 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f ng timer().. { o
05e0: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b stringstream os;
05f0: 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 os << " (" << i
0600: 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 nt((clock()-star
0610: 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 t_time)/CLOCKS_P
0620: 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 ER_SEC*1000) <<
0630: 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e " msec)"; return
0640: 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 os.str(); }..te
0650: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
0660: 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 T> ostream& oper
0670: 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 ator<<(ostream&
0680: 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 os, const vector
0690: 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c <T>& v).. { os <
06a0: 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 < "{ ";.. for(
06b0: 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c typename vector<
06c0: 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 T>::const_iterat
06d0: 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b or it=v.begin();
06e0: 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b it!=v.end(); ++
06f0: 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c it).. os << '\
0700: 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 "' << *it << '\"
0710: 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e ' << (it+1==v.en
0720: 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 d() ? "" : ", ")
0730: 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 ; os << " }"; re
0740: 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 turn os; }..void
0750: 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e verify_case(con
0760: 73 74 20 69 6e 74 26 20 45 78 70 65 63 74 65 64 st int& Expected
0770: 2c 20 63 6f 6e 73 74 20 69 6e 74 26 20 52 65 63 , const int& Rec
0780: 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 eived) {.. bool
0790: 6f 6b 20 3d 20 28 45 78 70 65 63 74 65 64 20 3d ok = (Expected =
07a0: 3d 20 52 65 63 65 69 76 65 64 29 3b 0d 0a 20 69 = Received);.. i
07b0: 66 28 6f 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 f(ok) cerr << "P
07c0: 41 53 53 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 ASSED" << timer(
07d0: 29 20 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 ) << endl; else
07e0: 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c { cerr << "FAIL
07f0: 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c ED" << timer() <
0800: 3c 20 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c < endl;.. cerr <
0810: 3c 20 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 < "\to: \"" << E
0820: 78 70 65 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 xpected << '\"'
0830: 3c 3c 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a << endl << "\tx:
0840: 20 5c 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 \"" << Received
0850: 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c << '\"' << endl
0860: 3b 20 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 ; } }..#define C
0870: 41 53 45 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 ASE(N) {cerr <<
0880: 22 54 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c "Test Case #" <<
0890: 20 4e 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 N << "..." << f
08a0: 6c 75 73 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 lush; start_time
08b0: 3d 63 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 =clock();..#defi
08c0: 6e 65 20 45 4e 44 09 20 76 65 72 69 66 79 5f 63 ne END. verify_c
08d0: 61 73 65 28 5f 2c 20 4d 69 6e 69 6e 67 47 6f 6c ase(_, MiningGol
08e0: 64 48 61 72 64 28 29 2e 47 65 74 4d 61 78 69 6d dHard().GetMaxim
08f0: 75 6d 47 6f 6c 64 28 4e 2c 20 4d 2c 20 65 76 65 umGold(N, M, eve
0900: 6e 74 5f 69 2c 20 65 76 65 6e 74 5f 6a 2c 20 65 nt_i, event_j, e
0910: 76 65 6e 74 5f 64 69 2c 20 65 76 65 6e 74 5f 64 vent_di, event_d
0920: 6a 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 j));}..int main(
0930: 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 ){....CASE(0)...
0940: 69 6e 74 20 4e 20 3d 20 33 3b 20 0d 0a 09 69 6e int N = 3; ...in
0950: 74 20 4d 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 t M = 3; ...int
0960: 65 76 65 6e 74 5f 69 5f 5b 5d 20 3d 20 7b 31 7d event_i_[] = {1}
0970: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0980: 74 3e 20 65 76 65 6e 74 5f 69 28 65 76 65 6e 74 t> event_i(event
0990: 5f 69 5f 2c 20 65 76 65 6e 74 5f 69 5f 2b 73 69 _i_, event_i_+si
09a0: 7a 65 6f 66 28 65 76 65 6e 74 5f 69 5f 29 2f 73 zeof(event_i_)/s
09b0: 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 69 5f 29 izeof(*event_i_)
09c0: 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f ); ...int event_
09d0: 6a 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a 09 20 20 j_[] = {1};...
09e0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 vector <int> eve
09f0: 6e 74 5f 6a 28 65 76 65 6e 74 5f 6a 5f 2c 20 65 nt_j(event_j_, e
0a00: 76 65 6e 74 5f 6a 5f 2b 73 69 7a 65 6f 66 28 65 vent_j_+sizeof(e
0a10: 76 65 6e 74 5f 6a 5f 29 2f 73 69 7a 65 6f 66 28 vent_j_)/sizeof(
0a20: 2a 65 76 65 6e 74 5f 6a 5f 29 29 3b 20 0d 0a 09 *event_j_)); ...
0a30: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 vector <int> eve
0a40: 6e 74 5f 64 69 3b 20 0d 0a 09 76 65 63 74 6f 72 nt_di; ...vector
0a50: 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 64 6a 3b <int> event_dj;
0a60: 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 36 3b 20 0d ...int _ = 6; .
0a70: 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 .END..CASE(1)...
0a80: 69 6e 74 20 4e 20 3d 20 33 3b 20 0d 0a 09 69 6e int N = 3; ...in
0a90: 74 20 4d 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 t M = 3; ...int
0aa0: 65 76 65 6e 74 5f 69 5f 5b 5d 20 3d 20 7b 30 2c event_i_[] = {0,
0ab0: 20 32 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 2};... vector
0ac0: 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 69 28 65 76 <int> event_i(ev
0ad0: 65 6e 74 5f 69 5f 2c 20 65 76 65 6e 74 5f 69 5f ent_i_, event_i_
0ae0: 2b 73 69 7a 65 6f 66 28 65 76 65 6e 74 5f 69 5f +sizeof(event_i_
0af0: 29 2f 73 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f )/sizeof(*event_
0b00: 69 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 i_)); ...int eve
0b10: 6e 74 5f 6a 5f 5b 5d 20 3d 20 7b 30 2c 20 32 7d nt_j_[] = {0, 2}
0b20: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0b30: 74 3e 20 65 76 65 6e 74 5f 6a 28 65 76 65 6e 74 t> event_j(event
0b40: 5f 6a 5f 2c 20 65 76 65 6e 74 5f 6a 5f 2b 73 69 _j_, event_j_+si
0b50: 7a 65 6f 66 28 65 76 65 6e 74 5f 6a 5f 29 2f 73 zeof(event_j_)/s
0b60: 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 6a 5f 29 izeof(*event_j_)
0b70: 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f ); ...int event_
0b80: 64 69 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a 09 20 di_[] = {1};...
0b90: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 vector <int> ev
0ba0: 65 6e 74 5f 64 69 28 65 76 65 6e 74 5f 64 69 5f ent_di(event_di_
0bb0: 2c 20 65 76 65 6e 74 5f 64 69 5f 2b 73 69 7a 65 , event_di_+size
0bc0: 6f 66 28 65 76 65 6e 74 5f 64 69 5f 29 2f 73 69 of(event_di_)/si
0bd0: 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 64 69 5f 29 zeof(*event_di_)
0be0: 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f ); ...int event_
0bf0: 64 6a 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a 09 20 dj_[] = {1};...
0c00: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 vector <int> ev
0c10: 65 6e 74 5f 64 6a 28 65 76 65 6e 74 5f 64 6a 5f ent_dj(event_dj_
0c20: 2c 20 65 76 65 6e 74 5f 64 6a 5f 2b 73 69 7a 65 , event_dj_+size
0c30: 6f 66 28 65 76 65 6e 74 5f 64 6a 5f 29 2f 73 69 of(event_dj_)/si
0c40: 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 64 6a 5f 29 zeof(*event_dj_)
0c50: 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 31 30 ); ...int _ = 10
0c60: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 ; ..END..CASE(2)
0c70: 0d 0a 09 69 6e 74 20 4e 20 3d 20 34 3b 20 0d 0a ...int N = 4; ..
0c80: 09 69 6e 74 20 4d 20 3d 20 32 3b 20 0d 0a 09 69 .int M = 2; ...i
0c90: 6e 74 20 65 76 65 6e 74 5f 69 5f 5b 5d 20 3d 20 nt event_i_[] =
0ca0: 7b 31 2c 20 34 2c 20 34 7d 3b 0d 0a 09 20 20 76 {1, 4, 4};... v
0cb0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e ector <int> even
0cc0: 74 5f 69 28 65 76 65 6e 74 5f 69 5f 2c 20 65 76 t_i(event_i_, ev
0cd0: 65 6e 74 5f 69 5f 2b 73 69 7a 65 6f 66 28 65 76 ent_i_+sizeof(ev
0ce0: 65 6e 74 5f 69 5f 29 2f 73 69 7a 65 6f 66 28 2a ent_i_)/sizeof(*
0cf0: 65 76 65 6e 74 5f 69 5f 29 29 3b 20 0d 0a 09 69 event_i_)); ...i
0d00: 6e 74 20 65 76 65 6e 74 5f 6a 5f 5b 5d 20 3d 20 nt event_j_[] =
0d10: 7b 31 2c 20 32 2c 20 30 7d 3b 0d 0a 09 20 20 76 {1, 2, 0};... v
0d20: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e ector <int> even
0d30: 74 5f 6a 28 65 76 65 6e 74 5f 6a 5f 2c 20 65 76 t_j(event_j_, ev
0d40: 65 6e 74 5f 6a 5f 2b 73 69 7a 65 6f 66 28 65 76 ent_j_+sizeof(ev
0d50: 65 6e 74 5f 6a 5f 29 2f 73 69 7a 65 6f 66 28 2a ent_j_)/sizeof(*
0d60: 65 76 65 6e 74 5f 6a 5f 29 29 3b 20 0d 0a 09 69 event_j_)); ...i
0d70: 6e 74 20 65 76 65 6e 74 5f 64 69 5f 5b 5d 20 3d nt event_di_[] =
0d80: 20 7b 31 2c 20 31 7d 3b 0d 0a 09 20 20 76 65 63 {1, 1};... vec
0d90: 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f tor <int> event_
0da0: 64 69 28 65 76 65 6e 74 5f 64 69 5f 2c 20 65 76 di(event_di_, ev
0db0: 65 6e 74 5f 64 69 5f 2b 73 69 7a 65 6f 66 28 65 ent_di_+sizeof(e
0dc0: 76 65 6e 74 5f 64 69 5f 29 2f 73 69 7a 65 6f 66 vent_di_)/sizeof
0dd0: 28 2a 65 76 65 6e 74 5f 64 69 5f 29 29 3b 20 0d (*event_di_)); .
0de0: 0a 09 69 6e 74 20 65 76 65 6e 74 5f 64 6a 5f 5b ..int event_dj_[
0df0: 5d 20 3d 20 7b 31 2c 20 31 7d 3b 0d 0a 09 20 20 ] = {1, 1};...
0e00: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 vector <int> eve
0e10: 6e 74 5f 64 6a 28 65 76 65 6e 74 5f 64 6a 5f 2c nt_dj(event_dj_,
0e20: 20 65 76 65 6e 74 5f 64 6a 5f 2b 73 69 7a 65 6f event_dj_+sizeo
0e30: 66 28 65 76 65 6e 74 5f 64 6a 5f 29 2f 73 69 7a f(event_dj_)/siz
0e40: 65 6f 66 28 2a 65 76 65 6e 74 5f 64 6a 5f 29 29 eof(*event_dj_))
0e50: 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 31 35 3b ; ...int _ = 15;
0e60: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d ..END..CASE(3).
0e70: 0a 09 69 6e 74 20 4e 20 3d 20 36 3b 20 0d 0a 09 ..int N = 6; ...
0e80: 69 6e 74 20 4d 20 3d 20 36 3b 20 0d 0a 09 69 6e int M = 6; ...in
0e90: 74 20 65 76 65 6e 74 5f 69 5f 5b 5d 20 3d 20 7b t event_i_[] = {
0ea0: 30 2c 20 32 2c 20 31 2c 20 35 2c 20 36 2c 20 34 0, 2, 1, 5, 6, 4
0eb0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0ec0: 6e 74 3e 20 65 76 65 6e 74 5f 69 28 65 76 65 6e nt> event_i(even
0ed0: 74 5f 69 5f 2c 20 65 76 65 6e 74 5f 69 5f 2b 73 t_i_, event_i_+s
0ee0: 69 7a 65 6f 66 28 65 76 65 6e 74 5f 69 5f 29 2f izeof(event_i_)/
0ef0: 73 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 69 5f sizeof(*event_i_
0f00: 29 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 )); ...int event
0f10: 5f 6a 5f 5b 5d 20 3d 20 7b 34 2c 20 33 2c 20 31 _j_[] = {4, 3, 1
0f20: 2c 20 36 2c 20 32 2c 20 30 7d 3b 0d 0a 09 20 20 , 6, 2, 0};...
0f30: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 vector <int> eve
0f40: 6e 74 5f 6a 28 65 76 65 6e 74 5f 6a 5f 2c 20 65 nt_j(event_j_, e
0f50: 76 65 6e 74 5f 6a 5f 2b 73 69 7a 65 6f 66 28 65 vent_j_+sizeof(e
0f60: 76 65 6e 74 5f 6a 5f 29 2f 73 69 7a 65 6f 66 28 vent_j_)/sizeof(
0f70: 2a 65 76 65 6e 74 5f 6a 5f 29 29 3b 20 0d 0a 09 *event_j_)); ...
0f80: 69 6e 74 20 65 76 65 6e 74 5f 64 69 5f 5b 5d 20 int event_di_[]
0f90: 3d 20 7b 32 2c 20 33 2c 20 31 2c 20 35 2c 20 36 = {2, 3, 1, 5, 6
0fa0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0fb0: 6e 74 3e 20 65 76 65 6e 74 5f 64 69 28 65 76 65 nt> event_di(eve
0fc0: 6e 74 5f 64 69 5f 2c 20 65 76 65 6e 74 5f 64 69 nt_di_, event_di
0fd0: 5f 2b 73 69 7a 65 6f 66 28 65 76 65 6e 74 5f 64 _+sizeof(event_d
0fe0: 69 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 76 65 6e i_)/sizeof(*even
0ff0: 74 5f 64 69 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 t_di_)); ...int
1000: 65 76 65 6e 74 5f 64 6a 5f 5b 5d 20 3d 20 7b 32 event_dj_[] = {2
1010: 2c 20 34 2c 20 30 2c 20 35 2c 20 31 7d 3b 0d 0a , 4, 0, 5, 1};..
1020: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1030: 65 76 65 6e 74 5f 64 6a 28 65 76 65 6e 74 5f 64 event_dj(event_d
1040: 6a 5f 2c 20 65 76 65 6e 74 5f 64 6a 5f 2b 73 69 j_, event_dj_+si
1050: 7a 65 6f 66 28 65 76 65 6e 74 5f 64 6a 5f 29 2f zeof(event_dj_)/
1060: 73 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 64 6a sizeof(*event_dj
1070: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 _)); ...int _ =
1080: 36 33 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 63; ..END..CASE(
1090: 34 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 37 32 3b 4)...int N = 72;
10a0: 20 0d 0a 09 69 6e 74 20 4d 20 3d 20 39 30 3b 20 ...int M = 90;
10b0: 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f 69 5f 5b ...int event_i_[
10c0: 5d 20 3d 20 7b 39 2c 20 39 2c 20 34 32 2c 20 36 ] = {9, 9, 42, 6
10d0: 34 2c 20 33 37 2c 20 34 2c 20 36 37 2c 20 36 35 4, 37, 4, 67, 65
10e0: 2c 20 32 30 2c 20 31 38 2c 20 32 35 2c 20 34 35 , 20, 18, 25, 45
10f0: 2c 20 31 39 2c 20 35 37 2c 20 33 34 2c 20 32 39 , 19, 57, 34, 29
1100: 2c 20 32 30 2c 20 34 33 2c 20 31 37 2c 20 34 36 , 20, 43, 17, 46
1110: 2c 20 36 31 2c 20 31 2c 20 31 38 2c 20 35 33 2c , 61, 1, 18, 53,
1120: 20 35 34 2c 20 32 33 2c 20 39 2c 20 36 39 2c 20 54, 23, 9, 69,
1130: 35 37 2c 20 34 34 2c 20 33 34 2c 20 35 30 2c 20 57, 44, 34, 50,
1140: 33 37 2c 20 34 2c 20 32 36 2c 20 31 2c 20 38 2c 37, 4, 26, 1, 8,
1150: 20 34 2c 20 36 36 7d 3b 0d 0a 09 20 20 76 65 63 4, 66};... vec
1160: 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f tor <int> event_
1170: 69 28 65 76 65 6e 74 5f 69 5f 2c 20 65 76 65 6e i(event_i_, even
1180: 74 5f 69 5f 2b 73 69 7a 65 6f 66 28 65 76 65 6e t_i_+sizeof(even
1190: 74 5f 69 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 76 t_i_)/sizeof(*ev
11a0: 65 6e 74 5f 69 5f 29 29 3b 20 0d 0a 09 69 6e 74 ent_i_)); ...int
11b0: 20 65 76 65 6e 74 5f 6a 5f 5b 5d 20 3d 20 7b 33 event_j_[] = {3
11c0: 37 2c 20 34 37 2c 20 34 38 2c 20 36 39 2c 20 35 7, 47, 48, 69, 5
11d0: 36 2c 20 32 32 2c 20 34 30 2c 20 35 32 2c 20 34 6, 22, 40, 52, 4
11e0: 33 2c 20 34 36 2c 20 36 34 2c 20 32 34 2c 20 34 3, 46, 64, 24, 4
11f0: 38 2c 20 35 34 2c 20 35 34 2c 20 35 36 2c 20 33 8, 54, 54, 56, 3
1200: 32 2c 20 37 37 2c 20 35 30 2c 20 38 2c 20 37 2c 2, 77, 50, 8, 7,
1210: 20 39 30 2c 20 35 35 2c 20 33 34 2c 20 34 30 2c 90, 55, 34, 40,
1220: 20 38 39 2c 20 35 37 2c 20 34 34 2c 20 32 31 2c 89, 57, 44, 21,
1230: 20 35 39 2c 20 38 39 2c 20 32 31 2c 20 36 39 2c 59, 89, 21, 69,
1240: 20 34 36 2c 20 30 2c 20 38 39 2c 20 33 31 2c 20 46, 0, 89, 31,
1250: 33 2c 20 35 30 7d 3b 0d 0a 09 20 20 76 65 63 74 3, 50};... vect
1260: 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 6a or <int> event_j
1270: 28 65 76 65 6e 74 5f 6a 5f 2c 20 65 76 65 6e 74 (event_j_, event
1280: 5f 6a 5f 2b 73 69 7a 65 6f 66 28 65 76 65 6e 74 _j_+sizeof(event
1290: 5f 6a 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 76 65 _j_)/sizeof(*eve
12a0: 6e 74 5f 6a 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 nt_j_)); ...int
12b0: 65 76 65 6e 74 5f 64 69 5f 5b 5d 20 3d 20 7b 35 event_di_[] = {5
12c0: 36 2c 20 35 2c 20 32 31 2c 20 35 2c 20 32 32 2c 6, 5, 21, 5, 22,
12d0: 20 35 2c 20 34 35 2c 20 34 2c 20 34 34 2c 20 32 5, 45, 4, 44, 2
12e0: 30 2c 20 36 38 2c 20 36 33 2c 20 33 37 2c 20 31 0, 68, 63, 37, 1
12f0: 34 2c 20 34 33 2c 20 33 31 2c 20 37 30 2c 20 32 4, 43, 31, 70, 2
1300: 38 2c 20 35 31 2c 20 33 38 2c 20 32 30 2c 20 35 8, 51, 38, 20, 5
1310: 39 2c 20 37 32 2c 20 36 36 2c 20 31 36 2c 20 32 9, 72, 66, 16, 2
1320: 30 2c 20 33 39 2c 20 37 32 2c 20 31 31 2c 20 37 0, 39, 72, 11, 7
1330: 31 2c 20 32 31 2c 20 35 31 2c 20 36 30 2c 20 34 1, 21, 51, 60, 4
1340: 32 2c 20 34 30 2c 20 31 30 2c 20 33 32 2c 20 37 2, 40, 10, 32, 7
1350: 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 0};... vector <
1360: 69 6e 74 3e 20 65 76 65 6e 74 5f 64 69 28 65 76 int> event_di(ev
1370: 65 6e 74 5f 64 69 5f 2c 20 65 76 65 6e 74 5f 64 ent_di_, event_d
1380: 69 5f 2b 73 69 7a 65 6f 66 28 65 76 65 6e 74 5f i_+sizeof(event_
1390: 64 69 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 76 65 di_)/sizeof(*eve
13a0: 6e 74 5f 64 69 5f 29 29 3b 20 0d 0a 09 69 6e 74 nt_di_)); ...int
13b0: 20 65 76 65 6e 74 5f 64 6a 5f 5b 5d 20 3d 20 7b event_dj_[] = {
13c0: 37 37 2c 20 37 33 2c 20 34 32 2c 20 38 30 2c 20 77, 73, 42, 80,
13d0: 34 33 2c 20 32 34 2c 20 38 31 2c 20 36 38 2c 20 43, 24, 81, 68,
13e0: 34 30 2c 20 38 36 2c 20 31 2c 20 37 36 2c 20 34 40, 86, 1, 76, 4
13f0: 33 2c 20 31 30 2c 20 34 33 2c 20 35 33 2c 20 34 3, 10, 43, 53, 4
1400: 30 2c 20 32 36 2c 20 31 38 2c 20 37 30 2c 20 36 0, 26, 18, 70, 6
1410: 30 2c 20 36 38 2c 20 32 39 2c 20 31 37 2c 20 36 0, 68, 29, 17, 6
1420: 36 2c 20 32 2c 20 38 37 2c 20 37 31 2c 20 39 30 6, 2, 87, 71, 90
1430: 2c 20 33 33 2c 20 31 31 2c 20 37 36 2c 20 36 39 , 33, 11, 76, 69
1440: 2c 20 31 37 2c 20 36 35 2c 20 32 31 2c 20 34 2c , 17, 65, 21, 4,
1450: 20 31 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 19};... vector
1460: 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 64 6a 28 <int> event_dj(
1470: 65 76 65 6e 74 5f 64 6a 5f 2c 20 65 76 65 6e 74 event_dj_, event
1480: 5f 64 6a 5f 2b 73 69 7a 65 6f 66 28 65 76 65 6e _dj_+sizeof(even
1490: 74 5f 64 6a 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 t_dj_)/sizeof(*e
14a0: 76 65 6e 74 5f 64 6a 5f 29 29 3b 20 0d 0a 09 69 vent_dj_)); ...i
14b0: 6e 74 20 5f 20 3d 20 35 38 31 30 3b 20 0d 0a 45 nt _ = 5810; ..E
14c0: 4e 44 0d 0a 43 41 53 45 28 35 29 0d 0a 09 69 6e ND..CASE(5)...in
14d0: 74 20 4e 20 3d 20 31 30 30 30 30 30 30 3b 20 0d t N = 1000000; .
14e0: 0a 09 69 6e 74 20 4d 20 3d 20 31 30 30 30 30 30 ..int M = 100000
14f0: 30 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f 0; ...int event_
1500: 69 5f 5b 5d 20 3d 20 7b 39 2c 20 39 2c 20 34 32 i_[] = {9, 9, 42
1510: 2c 20 36 34 2c 20 33 37 2c 20 34 2c 20 36 37 2c , 64, 37, 4, 67,
1520: 20 36 35 2c 20 32 30 2c 20 31 38 2c 20 32 35 2c 65, 20, 18, 25,
1530: 20 34 35 2c 20 31 39 2c 20 35 37 2c 20 33 34 2c 45, 19, 57, 34,
1540: 20 32 39 2c 20 32 30 2c 20 34 33 2c 20 31 37 2c 29, 20, 43, 17,
1550: 20 34 36 2c 20 36 31 2c 20 31 2c 20 31 38 2c 20 46, 61, 1, 18,
1560: 35 33 2c 20 35 34 2c 20 32 33 2c 20 39 2c 20 36 53, 54, 23, 9, 6
1570: 39 2c 20 35 37 2c 20 34 34 2c 20 33 34 2c 20 35 9, 57, 44, 34, 5
1580: 30 2c 20 33 37 2c 20 34 2c 20 32 36 2c 20 31 2c 0, 37, 4, 26, 1,
1590: 20 38 2c 20 34 2c 20 36 36 7d 3b 0d 0a 09 20 20 8, 4, 66};...
15a0: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 vector <int> eve
15b0: 6e 74 5f 69 28 65 76 65 6e 74 5f 69 5f 2c 20 65 nt_i(event_i_, e
15c0: 76 65 6e 74 5f 69 5f 2b 73 69 7a 65 6f 66 28 65 vent_i_+sizeof(e
15d0: 76 65 6e 74 5f 69 5f 29 2f 73 69 7a 65 6f 66 28 vent_i_)/sizeof(
15e0: 2a 65 76 65 6e 74 5f 69 5f 29 29 3b 20 0d 0a 09 *event_i_)); ...
15f0: 69 6e 74 20 65 76 65 6e 74 5f 6a 5f 5b 5d 20 3d int event_j_[] =
1600: 20 7b 33 37 2c 20 34 37 2c 20 34 38 2c 20 36 39 {37, 47, 48, 69
1610: 2c 20 35 36 2c 20 32 32 2c 20 34 30 2c 20 35 32 , 56, 22, 40, 52
1620: 2c 20 34 33 2c 20 34 36 2c 20 36 34 2c 20 32 34 , 43, 46, 64, 24
1630: 2c 20 34 38 2c 20 35 34 2c 20 35 34 2c 20 35 36 , 48, 54, 54, 56
1640: 2c 20 33 32 2c 20 37 37 2c 20 35 30 2c 20 38 2c , 32, 77, 50, 8,
1650: 20 37 2c 20 39 30 2c 20 35 35 2c 20 33 34 2c 20 7, 90, 55, 34,
1660: 34 30 2c 20 38 39 2c 20 35 37 2c 20 34 34 2c 20 40, 89, 57, 44,
1670: 32 31 2c 20 35 39 2c 20 38 39 2c 20 32 31 2c 20 21, 59, 89, 21,
1680: 36 39 2c 20 34 36 2c 20 30 2c 20 38 39 2c 20 33 69, 46, 0, 89, 3
1690: 31 2c 20 33 2c 20 35 30 7d 3b 0d 0a 09 20 20 76 1, 3, 50};... v
16a0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e ector <int> even
16b0: 74 5f 6a 28 65 76 65 6e 74 5f 6a 5f 2c 20 65 76 t_j(event_j_, ev
16c0: 65 6e 74 5f 6a 5f 2b 73 69 7a 65 6f 66 28 65 76 ent_j_+sizeof(ev
16d0: 65 6e 74 5f 6a 5f 29 2f 73 69 7a 65 6f 66 28 2a ent_j_)/sizeof(*
16e0: 65 76 65 6e 74 5f 6a 5f 29 29 3b 20 0d 0a 09 69 event_j_)); ...i
16f0: 6e 74 20 65 76 65 6e 74 5f 64 69 5f 5b 5d 20 3d nt event_di_[] =
1700: 20 7b 35 36 2c 20 35 2c 20 32 31 2c 20 35 2c 20 {56, 5, 21, 5,
1710: 32 32 2c 20 35 2c 20 34 35 2c 20 34 2c 20 34 34 22, 5, 45, 4, 44
1720: 2c 20 32 30 2c 20 36 38 2c 20 36 33 2c 20 33 37 , 20, 68, 63, 37
1730: 2c 20 31 34 2c 20 34 33 2c 20 33 31 2c 20 37 30 , 14, 43, 31, 70
1740: 2c 20 32 38 2c 20 35 31 2c 20 33 38 2c 20 32 30 , 28, 51, 38, 20
1750: 2c 20 35 39 2c 20 37 32 2c 20 36 36 2c 20 31 36 , 59, 72, 66, 16
1760: 2c 20 32 30 2c 20 33 39 2c 20 37 32 2c 20 31 31 , 20, 39, 72, 11
1770: 2c 20 37 31 2c 20 32 31 2c 20 35 31 2c 20 36 30 , 71, 21, 51, 60
1780: 2c 20 34 32 2c 20 34 30 2c 20 31 30 2c 20 33 32 , 42, 40, 10, 32
1790: 2c 20 37 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f , 70};... vecto
17a0: 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 64 69 r <int> event_di
17b0: 28 65 76 65 6e 74 5f 64 69 5f 2c 20 65 76 65 6e (event_di_, even
17c0: 74 5f 64 69 5f 2b 73 69 7a 65 6f 66 28 65 76 65 t_di_+sizeof(eve
17d0: 6e 74 5f 64 69 5f 29 2f 73 69 7a 65 6f 66 28 2a nt_di_)/sizeof(*
17e0: 65 76 65 6e 74 5f 64 69 5f 29 29 3b 20 0d 0a 09 event_di_)); ...
17f0: 69 6e 74 20 65 76 65 6e 74 5f 64 6a 5f 5b 5d 20 int event_dj_[]
1800: 3d 20 7b 37 37 2c 20 37 33 2c 20 34 32 2c 20 38 = {77, 73, 42, 8
1810: 30 2c 20 34 33 2c 20 32 34 2c 20 38 31 2c 20 36 0, 43, 24, 81, 6
1820: 38 2c 20 34 30 2c 20 38 36 2c 20 31 2c 20 37 36 8, 40, 86, 1, 76
1830: 2c 20 34 33 2c 20 31 30 2c 20 34 33 2c 20 35 33 , 43, 10, 43, 53
1840: 2c 20 34 30 2c 20 32 36 2c 20 31 38 2c 20 37 30 , 40, 26, 18, 70
1850: 2c 20 36 30 2c 20 36 38 2c 20 32 39 2c 20 31 37 , 60, 68, 29, 17
1860: 2c 20 36 36 2c 20 32 2c 20 38 37 2c 20 37 31 2c , 66, 2, 87, 71,
1870: 20 39 30 2c 20 33 33 2c 20 31 31 2c 20 37 36 2c 90, 33, 11, 76,
1880: 20 36 39 2c 20 31 37 2c 20 36 35 2c 20 32 31 2c 69, 17, 65, 21,
1890: 20 34 2c 20 31 39 7d 3b 0d 0a 09 20 20 76 65 63 4, 19};... vec
18a0: 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 5f tor <int> event_
18b0: 64 6a 28 65 76 65 6e 74 5f 64 6a 5f 2c 20 65 76 dj(event_dj_, ev
18c0: 65 6e 74 5f 64 6a 5f 2b 73 69 7a 65 6f 66 28 65 ent_dj_+sizeof(e
18d0: 76 65 6e 74 5f 64 6a 5f 29 2f 73 69 7a 65 6f 66 vent_dj_)/sizeof
18e0: 28 2a 65 76 65 6e 74 5f 64 6a 5f 29 29 3b 20 0d (*event_dj_)); .
18f0: 0a 09 69 6e 74 20 5f 20 3d 20 2d 31 3b 20 0d 0a ..int _ = -1; ..
1900: 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 36 29 END../*..CASE(6)
1910: 0d 0a 09 69 6e 74 20 4e 20 3d 20 31 30 30 30 30 ...int N = 10000
1920: 30 30 3b 20 0d 0a 09 69 6e 74 20 4d 20 3d 20 31 00; ...int M = 1
1930: 30 30 30 30 30 30 3b 20 0d 0a 09 69 6e 74 20 65 000000; ...int e
1940: 76 65 6e 74 5f 69 5f 5b 5d 20 3d 20 3b 0d 0a 09 vent_i_[] = ;...
1950: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 vector <int> e
1960: 76 65 6e 74 5f 69 28 65 76 65 6e 74 5f 69 5f 2c vent_i(event_i_,
1970: 20 65 76 65 6e 74 5f 69 5f 2b 73 69 7a 65 6f 66 event_i_+sizeof
1980: 28 65 76 65 6e 74 5f 69 5f 29 2f 73 69 7a 65 6f (event_i_)/sizeo
1990: 66 28 2a 65 76 65 6e 74 5f 69 5f 29 29 3b 20 0d f(*event_i_)); .
19a0: 0a 09 69 6e 74 20 65 76 65 6e 74 5f 6a 5f 5b 5d ..int event_j_[]
19b0: 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 = ;... vector
19c0: 3c 69 6e 74 3e 20 65 76 65 6e 74 5f 6a 28 65 76 <int> event_j(ev
19d0: 65 6e 74 5f 6a 5f 2c 20 65 76 65 6e 74 5f 6a 5f ent_j_, event_j_
19e0: 2b 73 69 7a 65 6f 66 28 65 76 65 6e 74 5f 6a 5f +sizeof(event_j_
19f0: 29 2f 73 69 7a 65 6f 66 28 2a 65 76 65 6e 74 5f )/sizeof(*event_
1a00: 6a 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 j_)); ...int eve
1a10: 6e 74 5f 64 69 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 nt_di_[] = ;...
1a20: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 vector <int> ev
1a30: 65 6e 74 5f 64 69 28 65 76 65 6e 74 5f 64 69 5f ent_di(event_di_
1a40: 2c 20 65 76 65 6e 74 5f 64 69 5f 2b 73 69 7a 65 , event_di_+size
1a50: 6f 66 28 65 76 65 6e 74 5f 64 69 5f 29 2f 73 69 of(event_di_)/si
1a60: 7a 65 6f 66 28 2a 65 76 65 6e 74 5f 64 69 5f 29 zeof(*event_di_)
1a70: 29 3b 20 0d 0a 09 69 6e 74 20 65 76 65 6e 74 5f ); ...int event_
1a80: 64 6a 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 dj_[] = ;... ve
1a90: 63 74 6f 72 20 3c 69 6e 74 3e 20 65 76 65 6e 74 ctor <int> event
1aa0: 5f 64 6a 28 65 76 65 6e 74 5f 64 6a 5f 2c 20 65 _dj(event_dj_, e
1ab0: 76 65 6e 74 5f 64 6a 5f 2b 73 69 7a 65 6f 66 28 vent_dj_+sizeof(
1ac0: 65 76 65 6e 74 5f 64 6a 5f 29 2f 73 69 7a 65 6f event_dj_)/sizeo
1ad0: 66 28 2a 65 76 65 6e 74 5f 64 6a 5f 29 29 3b 20 f(*event_dj_));
1ae0: 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 ...int _ = ; ..E
1af0: 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e ND..*/..}..// EN
1b00: 44 20 43 55 54 20 48 45 52 45 0d 0a D CUT HERE..