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 4c 69 6d 69 P;....class Limi
01a0: 74 65 64 4d 65 6d 6f 72 79 53 65 72 69 65 73 31 tedMemorySeries1
01b0: 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 6c 6f 6e { public:...lon
01c0: 67 20 6c 6f 6e 67 20 67 65 74 53 75 6d 28 69 6e g long getSum(in
01d0: 74 20 6e 2c 20 69 6e 74 20 78 30 2c 20 69 6e 74 t n, int x0, int
01e0: 20 61 2c 20 69 6e 74 20 62 2c 20 63 6f 6e 73 74 a, int b, const
01f0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 26 20 71 vector <int>& q
0200: 75 65 72 79 29 0d 0a 09 7b 0d 0a 09 09 4c 4c 20 uery)...{....LL
0210: 73 75 6d 20 3d 20 30 3b 0d 0a 09 09 6d 75 6c 74 sum = 0;....mult
0220: 69 73 65 74 3c 69 6e 74 3e 20 71 71 28 71 75 65 iset<int> qq(que
0230: 72 79 2e 62 65 67 69 6e 28 29 2c 20 71 75 65 72 ry.begin(), quer
0240: 79 2e 65 6e 64 28 29 29 3b 0d 0a 0d 0a 09 09 63 y.end());......c
0250: 6f 6e 73 74 20 69 6e 74 20 42 41 43 4b 45 54 20 onst int BACKET
0260: 3d 20 6d 69 6e 28 6e 2c 20 32 35 30 30 30 30 29 = min(n, 250000)
0270: 3b 0d 0a 09 09 69 6e 74 20 70 72 65 76 5f 74 75 ;....int prev_tu
0280: 72 6e 5f 6c 61 72 67 65 73 74 20 3d 20 2d 31 3b rn_largest = -1;
0290: 0d 0a 09 09 69 6e 74 20 70 74 6c 5f 63 6f 75 6e ....int ptl_coun
02a0: 74 20 3d 20 30 3b 0d 0a 0d 0a 09 09 69 6e 74 2a t = 0;......int*
02b0: 20 70 71 20 3d 20 6e 65 77 20 69 6e 74 5b 42 41 pq = new int[BA
02c0: 43 4b 45 54 2b 31 5d 3b 0d 0a 09 09 69 6e 74 20 CKET+1];....int
02d0: 70 71 6c 20 3d 20 30 3b 0d 0a 0d 0a 09 09 66 6f pql = 0;......fo
02e0: 72 28 69 6e 74 20 73 3d 30 3b 20 73 3c 6e 3b 20 r(int s=0; s<n;
02f0: 73 2b 3d 42 41 43 4b 45 54 29 20 7b 0d 0a 09 09 s+=BACKET) {....
0300: 09 70 71 6c 20 3d 20 30 3b 20 2f 2f 20 50 51 20 .pql = 0; // PQ
0310: 6b 65 65 70 69 6e 67 20 6d 69 6e 20 42 41 43 4b keeping min BACK
0320: 45 54 20 65 6c 65 6d 65 6e 74 73 0d 0a 0d 0a 09 ET elements.....
0330: 09 09 69 6e 74 20 76 20 3d 20 78 30 3b 0d 0a 09 ..int v = x0;...
0340: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0350: 3c 6e 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 09 <n; ++i) {......
0360: 69 66 28 76 20 3c 20 70 72 65 76 5f 74 75 72 6e if(v < prev_turn
0370: 5f 6c 61 72 67 65 73 74 29 20 7b 7d 0d 0a 09 09 _largest) {}....
0380: 09 09 65 6c 73 65 20 69 66 28 76 20 3d 3d 20 70 ..else if(v == p
0390: 72 65 76 5f 74 75 72 6e 5f 6c 61 72 67 65 73 74 rev_turn_largest
03a0: 20 26 26 20 70 74 6c 5f 63 6f 75 6e 74 3e 30 29 && ptl_count>0)
03b0: 20 7b 70 74 6c 5f 63 6f 75 6e 74 2d 2d 3b 7d 0d {ptl_count--;}.
03c0: 0a 09 09 09 09 65 6c 73 65 20 7b 0d 0a 09 09 09 .....else {.....
03d0: 09 09 70 71 5b 70 71 6c 2b 2b 5d 3d 76 3b 20 70 ..pq[pql++]=v; p
03e0: 75 73 68 5f 68 65 61 70 28 70 71 2b 30 2c 20 70 ush_heap(pq+0, p
03f0: 71 2b 70 71 6c 29 3b 0d 0a 09 09 09 09 09 69 66 q+pql);.......if
0400: 28 70 71 6c 3e 42 41 43 4b 45 54 29 0d 0a 09 09 (pql>BACKET)....
0410: 09 09 09 09 70 6f 70 5f 68 65 61 70 28 70 71 2b ....pop_heap(pq+
0420: 30 2c 20 70 71 2b 70 71 6c 29 2c 20 70 71 6c 2d 0, pq+pql), pql-
0430: 2d 3b 20 2f 2f 20 72 65 6d 6f 76 65 20 6c 61 72 -; // remove lar
0440: 67 65 73 74 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 gest......}.....
0450: 09 76 20 3d 20 69 6e 74 28 28 4c 4c 28 76 29 20 .v = int((LL(v)
0460: 2a 20 61 20 2b 20 62 29 20 25 20 31 30 30 30 30 * a + b) % 10000
0470: 30 30 30 30 37 29 3b 0d 0a 09 09 09 7d 0d 0a 09 00007);.....}...
0480: 09 09 69 6e 74 20 63 75 72 5f 6c 61 72 67 65 73 ..int cur_larges
0490: 74 20 3d 20 2d 31 3b 0d 0a 09 09 09 69 6e 74 20 t = -1;.....int
04a0: 63 6c 5f 63 6f 75 6e 74 20 3d 20 30 3b 0d 0a 0d cl_count = 0;...
04b0: 0a 09 09 09 66 6f 72 28 69 6e 74 20 72 61 6e 6b ....for(int rank
04c0: 3d 73 2b 70 71 6c 2d 31 3b 20 72 61 6e 6b 3e 3d =s+pql-1; rank>=
04d0: 73 3b 20 2d 2d 72 61 6e 6b 29 20 7b 0d 0a 09 09 s; --rank) {....
04e0: 09 09 69 6e 74 20 76 20 3d 20 70 71 5b 30 5d 3b ..int v = pq[0];
04f0: 0d 0a 09 09 09 09 70 6f 70 5f 68 65 61 70 28 70 ......pop_heap(p
0500: 71 2b 30 2c 20 70 71 2b 70 71 6c 29 2c 20 70 71 q+0, pq+pql), pq
0510: 6c 2d 2d 3b 0d 0a 0d 0a 09 09 09 09 69 66 28 63 l--;........if(c
0520: 75 72 5f 6c 61 72 67 65 73 74 20 3c 20 76 29 20 ur_largest < v)
0530: 63 75 72 5f 6c 61 72 67 65 73 74 20 3d 20 76 2c cur_largest = v,
0540: 20 63 6c 5f 63 6f 75 6e 74 20 3d 20 31 3b 0d 0a cl_count = 1;..
0550: 09 09 09 09 65 6c 73 65 20 69 66 28 63 75 72 5f ....else if(cur_
0560: 6c 61 72 67 65 73 74 20 3d 3d 20 76 29 20 63 6c largest == v) cl
0570: 5f 63 6f 75 6e 74 2b 2b 3b 0d 0a 0d 0a 09 09 09 _count++;.......
0580: 09 69 66 28 71 71 2e 63 6f 75 6e 74 28 72 61 6e .if(qq.count(ran
0590: 6b 29 29 20 7b 0d 0a 09 09 09 09 09 73 75 6d 20 k)) {.......sum
05a0: 2b 3d 20 4c 4c 28 76 29 20 2a 20 71 71 2e 63 6f += LL(v) * qq.co
05b0: 75 6e 74 28 72 61 6e 6b 29 3b 0d 0a 09 09 09 09 unt(rank);......
05c0: 09 71 71 2e 65 72 61 73 65 28 72 61 6e 6b 29 3b .qq.erase(rank);
05d0: 0d 0a 09 09 09 09 7d 0d 0a 09 09 09 7d 0d 0a 0d ......}.....}...
05e0: 0a 09 09 09 70 72 65 76 5f 74 75 72 6e 5f 6c 61 ....prev_turn_la
05f0: 72 67 65 73 74 20 3d 20 63 75 72 5f 6c 61 72 67 rgest = cur_larg
0600: 65 73 74 3b 0d 0a 09 09 09 70 74 6c 5f 63 6f 75 est;.....ptl_cou
0610: 6e 74 20 3d 20 63 6c 5f 63 6f 75 6e 74 3b 0d 0a nt = cl_count;..
0620: 09 09 7d 0d 0a 09 09 64 65 6c 65 74 65 5b 5d 20 ..}....delete[]
0630: 70 71 3b 0d 0a 09 09 72 65 74 75 72 6e 20 73 75 pq;....return su
0640: 6d 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f m;...}..};....//
0650: 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d BEGIN CUT HERE.
0660: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 .#include <ctime
0670: 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f >..double start_
0680: 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d time; string tim
0690: 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 er().. { ostring
06a0: 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c stream os; os <<
06b0: 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c " (" << int((cl
06c0: 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 ock()-start_time
06d0: 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 )/CLOCKS_PER_SEC
06e0: 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 *1000) << " msec
06f0: 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 )"; return os.st
0700: 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 r(); }..template
0710: 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 <typename T> ost
0720: 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c ream& operator<<
0730: 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f (ostream& os, co
0740: 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 nst vector<T>& v
0750: 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 ).. { os << "{ "
0760: 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 ;.. for(typena
0770: 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f me vector<T>::co
0780: 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d nst_iterator it=
0790: 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 v.begin(); it!=v
07a0: 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 .end(); ++it)..
07b0: 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 os << '\"' <<
07c0: 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 *it << '\"' << (
07d0: 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 it+1==v.end() ?
07e0: 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c "" : ", "); os <
07f0: 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f < " }"; return o
0800: 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 s; }..void verif
0810: 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 6c 6f 6e y_case(const lon
0820: 67 20 6c 6f 6e 67 26 20 45 78 70 65 63 74 65 64 g long& Expected
0830: 2c 20 63 6f 6e 73 74 20 6c 6f 6e 67 20 6c 6f 6e , const long lon
0840: 67 26 20 52 65 63 65 69 76 65 64 29 20 7b 0d 0a g& Received) {..
0850: 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 45 78 70 65 bool ok = (Expe
0860: 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 cted == Received
0870: 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 63 65 72 72 );.. if(ok) cerr
0880: 20 3c 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 << "PASSED" <<
0890: 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b timer() << endl;
08a0: 20 20 65 6c 73 65 20 7b 20 63 65 72 72 20 3c 3c else { cerr <<
08b0: 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 69 6d "FAILED" << tim
08c0: 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 0d 0a 20 er() << endl;..
08d0: 63 65 72 72 20 3c 3c 20 22 5c 74 6f 3a 20 5c 22 cerr << "\to: \"
08e0: 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 3c 3c " << Expected <<
08f0: 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 20 3c 3c '\"' << endl <<
0900: 20 22 5c 74 78 3a 20 5c 22 22 20 3c 3c 20 52 65 "\tx: \"" << Re
0910: 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c ceived << '\"' <
0920: 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 23 64 65 < endl; } }..#de
0930: 66 69 6e 65 20 43 41 53 45 28 4e 29 20 7b 63 65 fine CASE(N) {ce
0940: 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 rr << "Test Case
0950: 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 22 2e 2e 2e #" << N << "...
0960: 22 20 3c 3c 20 66 6c 75 73 68 3b 20 73 74 61 72 " << flush; star
0970: 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 0d t_time=clock();.
0980: 0a 23 64 65 66 69 6e 65 20 45 4e 44 09 20 76 65 .#define END. ve
0990: 72 69 66 79 5f 63 61 73 65 28 5f 2c 20 4c 69 6d rify_case(_, Lim
09a0: 69 74 65 64 4d 65 6d 6f 72 79 53 65 72 69 65 73 itedMemorySeries
09b0: 31 28 29 2e 67 65 74 53 75 6d 28 6e 2c 20 78 30 1().getSum(n, x0
09c0: 2c 20 61 2c 20 62 2c 20 71 75 65 72 79 29 29 3b , a, b, query));
09d0: 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a }..int main(){..
09e0: 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 ..CASE(0)...int
09f0: 6e 20 3d 20 35 3b 20 0d 0a 09 69 6e 74 20 78 30 n = 5; ...int x0
0a00: 20 3d 20 31 30 30 3b 20 0d 0a 09 69 6e 74 20 61 = 100; ...int a
0a10: 20 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 62 20 3d = 1; ...int b =
0a20: 20 35 3b 20 0d 0a 09 69 6e 74 20 71 75 65 72 79 5; ...int query
0a30: 5f 5b 5d 20 3d 20 7b 30 2c 33 7d 3b 0d 0a 09 20 _[] = {0,3};...
0a40: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 71 75 vector <int> qu
0a50: 65 72 79 28 71 75 65 72 79 5f 2c 20 71 75 65 72 ery(query_, quer
0a60: 79 5f 2b 73 69 7a 65 6f 66 28 71 75 65 72 79 5f y_+sizeof(query_
0a70: 29 2f 73 69 7a 65 6f 66 28 2a 71 75 65 72 79 5f )/sizeof(*query_
0a80: 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 )); ...long long
0a90: 20 5f 20 3d 20 32 31 35 4c 4c 3b 20 0d 0a 45 4e _ = 215LL; ..EN
0aa0: 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e 74 D..CASE(1)...int
0ab0: 20 6e 20 3d 20 35 3b 20 0d 0a 09 69 6e 74 20 78 n = 5; ...int x
0ac0: 30 20 3d 20 31 32 33 34 35 36 37 38 39 3b 20 0d 0 = 123456789; .
0ad0: 0a 09 69 6e 74 20 61 20 3d 20 39 38 37 36 35 34 ..int a = 987654
0ae0: 33 32 31 3b 20 0d 0a 09 69 6e 74 20 62 20 3d 20 321; ...int b =
0af0: 31 30 30 30 30 30 30 30 30 36 3b 20 0d 0a 09 69 1000000006; ...i
0b00: 6e 74 20 71 75 65 72 79 5f 5b 5d 20 3d 20 7b 30 nt query_[] = {0
0b10: 2c 31 2c 32 2c 33 7d 3b 0d 0a 09 20 20 76 65 63 ,1,2,3};... vec
0b20: 74 6f 72 20 3c 69 6e 74 3e 20 71 75 65 72 79 28 tor <int> query(
0b30: 71 75 65 72 79 5f 2c 20 71 75 65 72 79 5f 2b 73 query_, query_+s
0b40: 69 7a 65 6f 66 28 71 75 65 72 79 5f 29 2f 73 69 izeof(query_)/si
0b50: 7a 65 6f 66 28 2a 71 75 65 72 79 5f 29 29 3b 20 zeof(*query_));
0b60: 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d ...long long _ =
0b70: 20 37 33 33 30 32 38 36 39 32 4c 4c 3b 20 0d 0a 733028692LL; ..
0b80: 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 69 END..CASE(2)...i
0b90: 6e 74 20 6e 20 3d 20 35 30 30 30 30 30 30 3b 20 nt n = 5000000;
0ba0: 0d 0a 09 69 6e 74 20 78 30 20 3d 20 34 38 32 39 ...int x0 = 4829
0bb0: 39 35 38 33 37 3b 20 0d 0a 09 69 6e 74 20 61 20 95837; ...int a
0bc0: 3d 20 35 31 32 38 34 39 30 33 30 3b 20 0d 0a 09 = 512849030; ...
0bd0: 69 6e 74 20 62 20 3d 20 31 32 30 35 38 33 37 32 int b = 12058372
0be0: 34 3b 20 0d 0a 09 69 6e 74 20 71 75 65 72 79 5f 4; ...int query_
0bf0: 5b 5d 20 3d 20 7b 34 38 35 34 30 31 30 2c 33 31 [] = {4854010,31
0c00: 33 39 35 30 33 2c 31 38 35 35 35 34 36 2c 32 31 39503,1855546,21
0c10: 39 39 30 34 2c 38 34 36 33 35 37 2c 32 36 32 34 9904,846357,2624
0c20: 36 33 39 2c 38 39 31 32 36 30 2c 32 31 37 34 36 639,891260,21746
0c30: 37 2c 34 39 34 30 30 39 31 2c 34 38 30 32 37 36 7,4940091,480276
0c40: 30 2c 32 34 32 34 38 32 31 2c 34 32 34 30 37 36 0,2424821,424076
0c50: 2c 0d 0a 20 33 38 34 38 32 37 32 2c 32 30 36 32 ,.. 3848272,2062
0c60: 37 36 35 2c 32 39 32 32 34 30 37 2c 34 38 35 30 765,2922407,4850
0c70: 33 30 31 2c 31 32 37 39 39 37 32 2c 34 39 32 39 301,1279972,4929
0c80: 33 30 37 2c 32 30 33 35 34 35 36 2c 33 35 36 32 307,2035456,3562
0c90: 38 35 39 2c 31 37 34 39 35 39 34 2c 34 30 38 39 859,1749594,4089
0ca0: 34 39 39 2c 33 37 39 37 34 39 35 2c 31 30 31 33 499,3797495,1013
0cb0: 39 38 30 2c 0d 0a 20 31 36 35 30 38 30 35 2c 31 980,.. 1650805,1
0cc0: 32 34 35 32 31 33 2c 33 30 32 30 33 37 39 2c 34 245213,3020379,4
0cd0: 36 36 31 36 36 38 2c 34 32 37 31 37 30 2c 31 31 661668,427170,11
0ce0: 37 36 38 31 35 2c 32 39 32 39 34 34 2c 32 34 33 76815,292944,243
0cf0: 35 33 32 38 2c 34 32 30 38 30 39 2c 34 31 37 30 5328,420809,4170
0d00: 33 35 35 2c 32 36 33 35 31 39 37 2c 33 39 34 30 355,2635197,3940
0d10: 36 30 37 2c 0d 0a 20 34 33 31 31 37 31 38 2c 32 607,.. 4311718,2
0d20: 30 39 38 35 37 32 2c 34 38 36 38 30 35 34 2c 33 098572,4868054,3
0d30: 30 33 31 39 2c 34 35 38 38 39 36 39 2c 31 34 36 0319,4588969,146
0d40: 30 36 37 37 2c 31 33 33 35 30 32 38 2c 33 39 32 0677,1335028,392
0d50: 31 34 39 35 2c 33 36 32 31 39 37 30 2c 34 34 35 1495,3621970,445
0d60: 39 33 33 35 2c 39 36 36 30 30 30 2c 33 36 38 36 9335,966000,3686
0d70: 39 37 37 2c 0d 0a 20 32 33 31 36 35 36 30 2c 31 977,.. 2316560,1
0d80: 36 33 34 39 36 31 2c 32 32 38 30 36 32 34 2c 31 634961,2280624,1
0d90: 39 34 30 33 39 35 2c 33 33 32 31 35 34 36 2c 33 940395,3321546,3
0da0: 31 36 38 38 31 31 2c 31 38 35 36 35 34 37 2c 33 168811,1856547,3
0db0: 38 35 39 30 39 33 2c 34 33 34 30 34 37 35 2c 31 859093,4340475,1
0dc0: 33 38 32 37 38 32 2c 33 34 38 32 39 32 38 2c 32 382782,3482928,2
0dd0: 35 31 37 38 34 33 2c 0d 0a 20 31 38 35 30 30 38 517843,.. 185008
0de0: 2c 31 31 33 35 33 37 33 2c 32 38 32 31 30 35 30 ,1135373,2821050
0df0: 2c 33 32 36 30 34 38 34 2c 34 38 32 31 32 32 30 ,3260484,4821220
0e00: 2c 31 37 30 30 39 35 34 2c 33 32 34 33 33 34 33 ,1700954,3243343
0e10: 2c 32 31 38 33 36 31 35 2c 33 39 34 33 33 39 2c ,2183615,394339,
0e20: 32 36 33 30 31 32 31 2c 31 38 31 31 32 36 37 2c 2630121,1811267,
0e30: 31 30 36 30 35 34 32 2c 0d 0a 20 33 38 39 38 33 1060542,.. 38983
0e40: 31 34 2c 38 39 32 33 31 32 2c 32 30 31 35 35 38 14,892312,201558
0e50: 30 2c 31 31 31 36 31 2c 34 39 36 35 30 39 35 2c 0,11161,4965095,
0e60: 32 31 32 38 34 37 30 2c 32 33 32 30 39 33 33 2c 2128470,2320933,
0e70: 31 30 39 35 38 38 31 2c 33 39 33 38 34 35 30 2c 1095881,3938450,
0e80: 31 38 38 37 30 39 38 2c 39 37 35 34 32 36 2c 32 1887098,975426,2
0e90: 30 39 38 30 37 33 2c 33 33 30 30 39 33 37 2c 0d 098073,3300937,.
0ea0: 0a 20 31 31 34 35 35 36 30 2c 32 38 39 34 37 32 . 1145560,289472
0eb0: 38 2c 31 30 32 36 31 38 31 2c 33 32 35 39 34 30 8,1026181,325940
0ec0: 33 2c 34 35 30 39 33 34 35 2c 33 36 31 30 32 32 3,4509345,361022
0ed0: 34 2c 33 35 38 34 34 35 36 2c 31 38 37 37 34 38 4,3584456,187748
0ee0: 33 2c 32 36 36 35 37 35 32 2c 32 32 34 33 36 37 3,2665752,224367
0ef0: 31 2c 36 31 36 32 30 35 2c 35 30 34 38 34 39 2c 1,616205,504849,
0f00: 33 30 36 38 34 32 36 2c 0d 0a 20 31 34 37 31 39 3068426,.. 14719
0f10: 32 35 2c 34 31 34 34 35 36 38 7d 3b 0d 0a 09 20 25,4144568};...
0f20: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 71 75 vector <int> qu
0f30: 65 72 79 28 71 75 65 72 79 5f 2c 20 71 75 65 72 ery(query_, quer
0f40: 79 5f 2b 73 69 7a 65 6f 66 28 71 75 65 72 79 5f y_+sizeof(query_
0f50: 29 2f 73 69 7a 65 6f 66 28 2a 71 75 65 72 79 5f )/sizeof(*query_
0f60: 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 )); ...long long
0f70: 20 5f 20 3d 20 34 39 36 38 34 39 39 34 31 34 38 _ = 49684994148
0f80: 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 LL; ..END..CASE(
0f90: 32 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 35 30 30 2)...int n = 500
0fa0: 30 30 30 30 3b 20 0d 0a 09 69 6e 74 20 78 30 20 0000; ...int x0
0fb0: 3d 20 34 38 32 39 39 35 38 33 37 3b 20 0d 0a 09 = 482995837; ...
0fc0: 69 6e 74 20 61 20 3d 20 35 31 32 38 34 39 30 33 int a = 51284903
0fd0: 30 3b 20 0d 0a 09 69 6e 74 20 62 20 3d 20 31 32 0; ...int b = 12
0fe0: 30 35 38 33 37 32 34 3b 20 0d 0a 09 69 6e 74 20 0583724; ...int
0ff0: 71 75 65 72 79 5f 5b 5d 20 3d 20 7b 35 30 30 30 query_[] = {5000
1000: 30 30 30 2c 34 39 39 39 39 39 39 2c 34 39 39 39 000,4999999,4999
1010: 39 39 38 2c 34 39 39 39 39 39 37 2c 34 39 39 39 998,4999997,4999
1020: 39 39 36 2c 34 39 39 39 39 39 35 2c 34 39 39 39 996,4999995,4999
1030: 39 39 34 2c 34 39 39 39 39 39 33 2c 34 39 39 39 994,4999993,4999
1040: 39 39 32 2c 34 39 39 39 39 39 31 2c 34 39 39 39 992,4999991,4999
1050: 39 39 30 2c 34 39 39 39 39 38 39 2c 34 39 39 39 990,4999989,4999
1060: 39 38 38 2c 34 39 39 39 39 38 37 2c 34 39 39 39 988,4999987,4999
1070: 39 38 36 2c 34 39 39 39 39 38 35 2c 34 39 39 39 986,4999985,4999
1080: 39 38 34 2c 34 39 39 39 39 38 33 2c 34 39 39 39 984,4999983,4999
1090: 39 38 32 2c 34 39 39 39 39 38 31 2c 34 39 39 39 982,4999981,4999
10a0: 39 38 30 2c 34 39 39 39 39 37 39 2c 34 39 39 39 980,4999979,4999
10b0: 39 37 38 2c 34 39 39 39 39 37 37 2c 34 39 39 39 978,4999977,4999
10c0: 39 37 36 2c 34 39 39 39 39 37 35 2c 34 39 39 39 976,4999975,4999
10d0: 39 37 34 2c 34 39 39 39 39 37 33 2c 34 39 39 39 974,4999973,4999
10e0: 39 37 32 2c 34 39 39 39 39 37 31 2c 34 39 39 39 972,4999971,4999
10f0: 39 37 30 2c 34 39 39 39 39 36 39 2c 34 39 39 39 970,4999969,4999
1100: 39 36 38 2c 34 39 39 39 39 36 37 2c 34 39 39 39 968,4999967,4999
1110: 39 36 36 2c 34 39 39 39 39 36 35 2c 34 39 39 39 966,4999965,4999
1120: 39 36 34 2c 34 39 39 39 39 36 33 2c 34 39 39 39 964,4999963,4999
1130: 39 36 32 2c 34 39 39 39 39 36 31 2c 34 39 39 39 962,4999961,4999
1140: 39 36 30 2c 34 39 39 39 39 35 39 2c 34 39 39 39 960,4999959,4999
1150: 39 35 38 2c 34 39 39 39 39 35 37 2c 34 39 39 39 958,4999957,4999
1160: 39 35 36 2c 34 39 39 39 39 35 35 2c 34 39 39 39 956,4999955,4999
1170: 39 35 34 2c 34 39 39 39 39 35 33 2c 34 39 39 39 954,4999953,4999
1180: 39 35 32 2c 34 39 39 39 39 35 31 2c 34 39 39 39 952,4999951,4999
1190: 39 35 30 2c 34 39 39 39 39 34 39 2c 34 39 39 39 950,4999949,4999
11a0: 39 34 38 2c 34 39 39 39 39 34 37 2c 34 39 39 39 948,4999947,4999
11b0: 39 34 36 2c 34 39 39 39 39 34 35 2c 34 39 39 39 946,4999945,4999
11c0: 39 34 34 2c 34 39 39 39 39 34 33 2c 34 39 39 39 944,4999943,4999
11d0: 39 34 32 2c 34 39 39 39 39 34 31 2c 34 39 39 39 942,4999941,4999
11e0: 39 34 30 2c 34 39 39 39 39 33 39 2c 34 39 39 39 940,4999939,4999
11f0: 39 33 38 2c 34 39 39 39 39 33 37 2c 34 39 39 39 938,4999937,4999
1200: 39 33 36 2c 34 39 39 39 39 33 35 2c 34 39 39 39 936,4999935,4999
1210: 39 33 34 2c 34 39 39 39 39 33 33 2c 34 39 39 39 934,4999933,4999
1220: 39 33 32 2c 34 39 39 39 39 33 31 2c 34 39 39 39 932,4999931,4999
1230: 39 33 30 2c 34 39 39 39 39 32 39 2c 34 39 39 39 930,4999929,4999
1240: 39 32 38 2c 34 39 39 39 39 32 37 2c 34 39 39 39 928,4999927,4999
1250: 39 32 36 2c 34 39 39 39 39 32 35 2c 34 39 39 39 926,4999925,4999
1260: 39 32 34 2c 34 39 39 39 39 32 33 2c 34 39 39 39 924,4999923,4999
1270: 39 32 32 2c 34 39 39 39 39 32 31 2c 34 39 39 39 922,4999921,4999
1280: 39 32 30 2c 34 39 39 39 39 31 39 2c 34 39 39 39 920,4999919,4999
1290: 39 31 38 2c 34 39 39 39 39 31 37 2c 34 39 39 39 918,4999917,4999
12a0: 39 31 36 2c 34 39 39 39 39 31 35 2c 34 39 39 39 916,4999915,4999
12b0: 39 31 34 2c 34 39 39 39 39 31 33 2c 34 39 39 39 914,4999913,4999
12c0: 39 31 32 2c 34 39 39 39 39 31 31 2c 34 39 39 39 912,4999911,4999
12d0: 39 31 30 2c 34 39 39 39 39 30 39 2c 34 39 39 39 910,4999909,4999
12e0: 39 30 38 2c 34 39 39 39 39 30 37 2c 34 39 39 39 908,4999907,4999
12f0: 39 30 36 2c 34 39 39 39 39 30 35 2c 34 39 39 39 906,4999905,4999
1300: 39 30 34 2c 34 39 39 39 39 30 33 2c 34 39 39 39 904,4999903,4999
1310: 39 30 32 2c 34 39 39 39 39 30 31 7d 3b 0d 0a 09 902,4999901};...
1320: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 71 vector <int> q
1330: 75 65 72 79 28 71 75 65 72 79 5f 2c 20 71 75 65 uery(query_, que
1340: 72 79 5f 2b 73 69 7a 65 6f 66 28 71 75 65 72 79 ry_+sizeof(query
1350: 5f 29 2f 73 69 7a 65 6f 66 28 2a 71 75 65 72 79 _)/sizeof(*query
1360: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
1370: 67 20 5f 20 3d 20 2d 31 4c 4c 3b 20 0d 0a 45 4e g _ = -1LL; ..EN
1380: 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 33 29 0d 0a D../*..CASE(3)..
1390: 09 69 6e 74 20 6e 20 3d 20 3b 20 0d 0a 09 69 6e .int n = ; ...in
13a0: 74 20 78 30 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 t x0 = ; ...int
13b0: 61 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 62 20 3d a = ; ...int b =
13c0: 20 3b 20 0d 0a 09 69 6e 74 20 71 75 65 72 79 5f ; ...int query_
13d0: 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f [] = ;... vecto
13e0: 72 20 3c 69 6e 74 3e 20 71 75 65 72 79 28 71 75 r <int> query(qu
13f0: 65 72 79 5f 2c 20 71 75 65 72 79 5f 2b 73 69 7a ery_, query_+siz
1400: 65 6f 66 28 71 75 65 72 79 5f 29 2f 73 69 7a 65 eof(query_)/size
1410: 6f 66 28 2a 71 75 65 72 79 5f 29 29 3b 20 0d 0a of(*query_)); ..
1420: 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 4c .long long _ = L
1430: 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 L; ..END..CASE(4
1440: 29 0d 0a 09 69 6e 74 20 6e 20 3d 20 3b 20 0d 0a )...int n = ; ..
1450: 09 69 6e 74 20 78 30 20 3d 20 3b 20 0d 0a 09 69 .int x0 = ; ...i
1460: 6e 74 20 61 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 nt a = ; ...int
1470: 62 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 71 75 65 b = ; ...int que
1480: 72 79 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 ry_[] = ;... ve
1490: 63 74 6f 72 20 3c 69 6e 74 3e 20 71 75 65 72 79 ctor <int> query
14a0: 28 71 75 65 72 79 5f 2c 20 71 75 65 72 79 5f 2b (query_, query_+
14b0: 73 69 7a 65 6f 66 28 71 75 65 72 79 5f 29 2f 73 sizeof(query_)/s
14c0: 69 7a 65 6f 66 28 2a 71 75 65 72 79 5f 29 29 3b izeof(*query_));
14d0: 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 ...long long _
14e0: 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d = LL; ..END..*/.
14f0: 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 .}..// END CUT H
1500: 45 52 45 0d 0a ERE..