API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 13th, 2017
248
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.02 KB | None | 0 0
raw download clone embed print report
  1. #pragma comment(linker, "/stack:20000000")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  4.  
  5. #define _CRT_SECURE_NO_WARNINGS
  6. # include <iostream>
  7. # include <cmath>
  8. # include <algorithm>
  9. # include <stdio.h>
  10. # include <cstdint>
  11. # include <cstring>
  12. # include <string>
  13. # include <cstdlib>
  14. # include <vector>
  15. # include <bitset>
  16. # include <map>
  17. # include <queue>
  18. # include <ctime>
  19. # include <stack>
  20. # include <set>
  21. # include <list>
  22. # include <random>
  23. # include <deque>
  24. # include <functional>
  25. # include <iomanip>
  26. # include <sstream>
  27. # include <fstream>
  28. # include <complex>
  29. # include <numeric>
  30. # include <immintrin.h>
  31. # include <cassert>
  32. # include <array>
  33.  
  34. using namespace std;
  35.  
  36. // Let's define unordered map
  37. # ifdef __GNUC__
  38. # if __cplusplus > 199711L
  39. # include <unordered_set>
  40. # include <unordered_map>
  41. # else
  42. # include <tr1/unordered_map>
  43. # include <tr1/unordered_set>
  44. using namespace tr1;
  45. # endif
  46. # else
  47. # include <unordered_map>
  48. # include <unordered_set>
  49. # endif
  50.  
  51. #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
  52. #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  53. #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
  54. #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  55. #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  56. #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  57. #define macro_dispatcher___(macro, nargs) macro ## nargs
  58. #define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
  59. #define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  60. #define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  61. #define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  62. #define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  63. #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
  64. #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  65. #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
  66. #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
  67.  
  68. #ifdef _MSC_VER
  69. #define ALIGN(x) __declspec(align(x))
  70. #define PREFETCH(ptr, rw, level) ((void)0)
  71. #else
  72. #define ALIGN(x) __attribute__((aligned(x)))
  73. #define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
  74. #endif
  75.  
  76. #ifdef LOCAL
  77. #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
  78. #else
  79. #define CURTIME() ;
  80. #endif
  81. double __begin;
  82. #define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
  83.  
  84. #define mp make_pair
  85. typedef long long ll;
  86. typedef unsigned int uint;
  87. typedef unsigned long long ull;
  88. typedef pair<int, int> pii;
  89. typedef pair<long long, long long> pll;
  90. typedef vector<int> vi;
  91. typedef vector<long long> vll;
  92. typedef int itn;
  93.  
  94. template<class T1, class T2, class T3>
  95. struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  96. template<class T1, class T2, class T3>
  97. bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
  98. template<class T1, class T2, class T3>
  99. bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
  100. #define tri triple<int,int,int>
  101. #define trll triple<ll,ll,ll>
  102.  
  103. #define FI(n) for(int i=0;i<(n);++i)
  104. #define FJ(n) for(int j=0;j<(n);++j)
  105. #define FK(n) for(int k=0;k<(n);++k)
  106. #define FL(n) for(int l=0;l<(n);++l)
  107. #define FQ(n) for(int q=0;q<(n);++q)
  108. #define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
  109. #define all(a) std::begin(a), std::end(a)
  110. #define reunique(v) v.resize(unique(v.begin(), v.end()) - v.begin())
  111.  
  112. #define sqr(x) ((x) * (x))
  113. #define sqrt(x) sqrt(1.0 * (x))
  114. #define pow(x, n) pow(1.0 * (x), n)
  115.  
  116. #define COMPARE(obj) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b)
  117. #define COMPARE_BY(obj, field) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b) { return a.field < b.field; }
  118.  
  119. #define checkbit(n, b) (((n) >> (b)) & 1)
  120. #define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  121. #define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  122. #define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  123. inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
  124. inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
  125. unsigned int reverseBits(uint x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  126. template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
  127. inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  128. template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
  129. unsigned long long rdtsc() { unsigned long long ret = 0;
  130. #ifndef _MSC_VER
  131. __asm__ __volatile__("rdtsc" : "=A" (ret) : :);
  132. #endif
  133. return ret; }
  134. // Fast IO ********************************************************************************************************
  135. template<class T = int> T read_int() {
  136.     const int B = 4096;
  137.     static char b[B + 16], *e = b + B, *i = e;
  138.     auto c = [&]() { if (i == e) memset(b, 0, B), cin.read(b, B), i = b; };
  139.     c();
  140.     while (*i && (*i < '0' || *i > '9') && *i != '-') ++i;
  141.     c();
  142.     bool m = false;
  143.     if (*i == '-') ++i, c(), m = true;
  144.     T r = 0;
  145.     while (*i >= '0' && *i <= '9') r = r * 10 + *i - '0', ++i, c();
  146.     ++i;
  147.     return m ? -r : r;
  148. }
  149. const int __BS = 4096;
  150. static char __bu[__BS + 20], *__iw = __bu, *__e = __bu + __BS;
  151. template<class T>
  152. void write_int(T x, char endc = '\n') {
  153.     if (x < 0) *__iw++ = '-', x = -x;
  154.     if (x == 0) *__iw++ = '0';
  155.     char* s = __iw;
  156.     while (x) {
  157.         T t = x / 10;
  158.         char c = x - 10 * t + '0';
  159.         *__iw++ = c;
  160.         x = t;
  161.     }
  162.     char* f = __iw - 1;
  163.     while (s < f) swap(*s, *f), ++s, --f;
  164.     if (__iw > __e) cout.write(__bu, __iw - __bu), __iw = __bu;
  165.     *__iw++ = endc;
  166. }
  167. struct F { ~F() { if (__iw != __bu) cout.write(__bu, __iw - __bu); } };
  168. static F flush;
  169.  
  170. //STL output *****************************************************************************************************
  171. #define TT1 template<class T>
  172. #define TT1T2 template<class T1, class T2>
  173. #define TT1T2T3 template<class T1, class T2, class T3>
  174. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
  175. TT1 ostream& operator << (ostream& os, const vector<T>& v);
  176. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
  177. TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
  178. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
  179. TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
  180. TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
  181. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
  182. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
  183. TT1 ostream& operator << (ostream& os, const vector<T>& v){       bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  184. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){    bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  185. TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  186. TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  187. TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  188. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
  189. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  190. TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  191.  
  192. //STL input *****************************************************************************************************
  193. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
  194. TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
  195. TT1 inline istream& operator >> (istream& os, vector<T>& v) {
  196.     if (v.size()) for (T& t : v) os >> t; else {
  197.         string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
  198.         stringstream ss(s); while (ss >> obj) v.push_back(obj);
  199.     }
  200.     return os;
  201. }
  202. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
  203.  
  204. //Pair magic *****************************************************************************************************
  205. #define PT1T2 pair<T1, T2>
  206. TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
  207. TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
  208. TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
  209. TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
  210.  
  211. #undef TT1
  212. #undef TT1T2
  213. #undef TT1T2T3
  214.  
  215. #define FREIN(FILE) freopen(FILE, "rt", stdin)
  216. #define FREOUT(FILE) freopen(FILE, "wt", stdout)
  217.  
  218. template<class T> inline void normmod(T &x, T m) { x %= m; if (x < 0) x += m; }
  219. template<class T1, class T2> inline T2 summodfast(T1 x, T1 y, T2 m) { T2 res = x + y; if (res >= m) res -= m; return res; }
  220. template<class T1, class T2, class T3> inline void addmodfast(T1 &x, T2 y, T3 m) { x += y; if (x >= m) x -= m; }
  221. template<class T1, class T2, class T3> inline void submodfast(T1 &x, T2 y, T3 m) { x -= y; if (x < 0) x += m; }
  222. #if INTPTR_MAX == INT32_MAX
  223. inline ll mulmod(ll x, ll n, ll m){ ll r = 0; normmod(x, m); normmod(n, m); while (n) { if (n & 1) addmodfast(r, x, m); addmodfast(x, x, m); n /= 2; } return r; }
  224. #else
  225. inline ll mulmod(ll x, ll n, ll m){ return __int128(x) * n % m; }
  226. #endif
  227. inline ll powmod(ll x, ll n, ll m){ ll r = 1; normmod(x, m); while (n){ if (n & 1)r = (r*x) % m; x = (x*x) % m; n /= 2; }return r; }
  228. inline ll powmulmod(ll x, ll n, ll m) { ll res = 1; normmod(x, m); while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n /= 2; } return res; }
  229. template<class T> inline T gcd(T a, T b) { while (b) { a %= b; T t = a; a = b; b = t; } return a; }
  230. inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
  231. template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
  232. ll gcdex(ll a, ll b, ll& x, ll& y) {
  233.     if (!a) { x = 0; y = 1; return b; }
  234.     ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
  235.     return d;
  236. }
  237. template<class T> bool isPrime(T x) { if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  238.     for (T i = 4; i * i <= x; i += 2) if (x % i == 0) return 0; return 1; }
  239. bool millerRabin(long long n) {
  240.     if (n <= 1000) return isPrime(n);
  241.     long long s = n - 1; int t = 0; while (s % 2 == 0) s /= 2, ++t;
  242.     for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
  243.         long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
  244.         for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
  245.         return false; nextp:;
  246.     } return true;
  247. }
  248.  
  249. // Useful constants
  250.  
  251. //int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431, 1000000123};
  252. #define INF         1011111111
  253. #define LLINF       1000111000111000111LL
  254. #define EPS         (double)1e-10
  255. #define mod         998244353
  256. #define PI          3.14159265358979323846264
  257. #define link        asaxlajrewqwe
  258. #define rank        wahayawehasdakw
  259. //*************************************************************************************
  260.  
  261. int32_t solve();
  262. int32_t main() {
  263.     ios_base::sync_with_stdio(0);cin.tie(0);
  264. #ifdef LOCAL
  265.     FREIN("input.txt");
  266. //    FREOUT("out.txt");
  267. #endif
  268.     return solve();
  269. }
  270.  
  271. int a[101011];
  272. const int BS = 1 << 14;
  273. bool used[BS + 7];
  274. vector<int> blocks[100000 / BS + 11];
  275. vector<int> positions[100000 / BS + 13];
  276. int32_t solve() {
  277.     int n;
  278.     cin >> n;
  279.     std::mt19937 gen;
  280.     auto Rnd = [&](int l, int r) {
  281.         return std::uniform_int_distribution<int>(l, r)(gen);
  282.     };
  283.     for (int i = 0; i < n; ++i) {
  284.         a[i] = Rnd(0, n - 1);
  285.         blocks[a[i] / BS].push_back(a[i] % BS);
  286.         positions[a[i] / BS].push_back(i);
  287.     }
  288.     int q;
  289.     cin >> q;
  290.     long long ans = 0;
  291.     const int K = 40;
  292.     while (q--) {
  293.         int l1 = Rnd(0, n / K);
  294.         int r1 = n / 2 - Rnd(0, n / K);
  295.         int l2 = n / 2 + Rnd(1, n / K);
  296.         int r2 = n - Rnd(1, n / K);
  297.         int res = 0;
  298.         for (int j = 0; j * BS < n; ++j) {
  299.             memset(used, 0, BS);
  300.             auto& b = blocks[j];
  301.             for (pii p : {pii(l1, r1), pii(l2, r2)}) {
  302.                 int from = int(lower_bound(positions[j].begin(), positions[j].end(), p.first) - positions[j].begin());
  303.                 int to = int(upper_bound(positions[j].begin(), positions[j].end(), p.second) - positions[j].begin());
  304.                 auto ptr = b.data() + from;
  305.                 int cnt = to - from;
  306.                 int c4 = cnt / 4;
  307.                 while (c4--) {
  308.                     res += used[ptr[0]];
  309.                     used[ptr[0]] = 1;
  310.                     res += used[ptr[1]];
  311.                     used[ptr[1]] = 1;
  312.                     res += used[ptr[2]];
  313.                     used[ptr[2]] = 1;
  314.                     res += used[ptr[3]];
  315.                     used[ptr[3]] = 1;
  316.                     ptr += 4;
  317.                 }
  318.                 cnt %= 4;
  319.                 while (cnt--) {
  320.                     auto x = *ptr++;
  321.                     res += used[x];
  322.                     used[x] = true;
  323.                 }
  324.             }
  325.         }
  326.         ans += r1 - l1 + r2 - l2 + 2 - res;
  327.     }
  328.     cout << ans << endl;
  329.     CURTIME();
  330.     return 0;
  331. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!