Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/stack:20000000")
- #pragma GCC optimize("Ofast")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
- #define _CRT_SECURE_NO_WARNINGS
- # include <iostream>
- # include <cmath>
- # include <algorithm>
- # include <stdio.h>
- # include <cstdint>
- # include <cstring>
- # include <string>
- # include <cstdlib>
- # include <vector>
- # include <bitset>
- # include <map>
- # include <queue>
- # include <ctime>
- # include <stack>
- # include <set>
- # include <list>
- # include <random>
- # include <deque>
- # include <functional>
- # include <iomanip>
- # include <sstream>
- # include <fstream>
- # include <complex>
- # include <numeric>
- # include <immintrin.h>
- # include <cassert>
- # include <array>
- using namespace std;
- // Let's define unordered map
- # ifdef __GNUC__
- # if __cplusplus > 199711L
- # include <unordered_set>
- # include <unordered_map>
- # else
- # include <tr1/unordered_map>
- # include <tr1/unordered_set>
- using namespace tr1;
- # endif
- # else
- # include <unordered_map>
- # include <unordered_set>
- # endif
- #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
- #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
- #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
- #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
- #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
- #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
- #define macro_dispatcher___(macro, nargs) macro ## nargs
- #define DBN1(a) cerr<<#a<<"="<<(a)<<"\n"
- #define DBN2(a,b) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
- #define DBN3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
- #define DBN4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
- #define DBN5(a,b,c,d,e) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
- #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
- #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
- #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
- #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
- #ifdef _MSC_VER
- #define ALIGN(x) __declspec(align(x))
- #define PREFETCH(ptr, rw, level) ((void)0)
- #else
- #define ALIGN(x) __attribute__((aligned(x)))
- #define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
- #endif
- #ifdef LOCAL
- #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
- #else
- #define CURTIME() ;
- #endif
- double __begin;
- #define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
- #define mp make_pair
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- typedef pair<long long, long long> pll;
- typedef vector<int> vi;
- typedef vector<long long> vll;
- typedef int itn;
- template<class T1, class T2, class T3>
- 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){} };
- template<class T1, class T2, class T3>
- 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;}
- template<class T1, class T2, class T3>
- 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;}
- #define tri triple<int,int,int>
- #define trll triple<ll,ll,ll>
- #define FI(n) for(int i=0;i<(n);++i)
- #define FJ(n) for(int j=0;j<(n);++j)
- #define FK(n) for(int k=0;k<(n);++k)
- #define FL(n) for(int l=0;l<(n);++l)
- #define FQ(n) for(int q=0;q<(n);++q)
- #define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
- #define all(a) std::begin(a), std::end(a)
- #define reunique(v) v.resize(unique(v.begin(), v.end()) - v.begin())
- #define sqr(x) ((x) * (x))
- #define sqrt(x) sqrt(1.0 * (x))
- #define pow(x, n) pow(1.0 * (x), n)
- #define COMPARE(obj) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b)
- #define COMPARE_BY(obj, field) [&](const std::decay<decltype(obj)>::type& a, const std::decay<decltype(obj)>::type& b) { return a.field < b.field; }
- #define checkbit(n, b) (((n) >> (b)) & 1)
- #define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- #define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- #define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
- inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
- 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)); }
- template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
- inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
- 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; }
- unsigned long long rdtsc() { unsigned long long ret = 0;
- #ifndef _MSC_VER
- __asm__ __volatile__("rdtsc" : "=A" (ret) : :);
- #endif
- return ret; }
- // Fast IO ********************************************************************************************************
- template<class T = int> T read_int() {
- const int B = 4096;
- static char b[B + 16], *e = b + B, *i = e;
- auto c = [&]() { if (i == e) memset(b, 0, B), cin.read(b, B), i = b; };
- c();
- while (*i && (*i < '0' || *i > '9') && *i != '-') ++i;
- c();
- bool m = false;
- if (*i == '-') ++i, c(), m = true;
- T r = 0;
- while (*i >= '0' && *i <= '9') r = r * 10 + *i - '0', ++i, c();
- ++i;
- return m ? -r : r;
- }
- const int __BS = 4096;
- static char __bu[__BS + 20], *__iw = __bu, *__e = __bu + __BS;
- template<class T>
- void write_int(T x, char endc = '\n') {
- if (x < 0) *__iw++ = '-', x = -x;
- if (x == 0) *__iw++ = '0';
- char* s = __iw;
- while (x) {
- T t = x / 10;
- char c = x - 10 * t + '0';
- *__iw++ = c;
- x = t;
- }
- char* f = __iw - 1;
- while (s < f) swap(*s, *f), ++s, --f;
- if (__iw > __e) cout.write(__bu, __iw - __bu), __iw = __bu;
- *__iw++ = endc;
- }
- struct F { ~F() { if (__iw != __bu) cout.write(__bu, __iw - __bu); } };
- static F flush;
- //STL output *****************************************************************************************************
- #define TT1 template<class T>
- #define TT1T2 template<class T1, class T2>
- #define TT1T2T3 template<class T1, class T2, class T3>
- TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
- TT1 ostream& operator << (ostream& os, const vector<T>& v);
- TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
- TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
- TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
- TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
- TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
- TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
- TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
- 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 << "]"; }
- 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 << "]"; }
- 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 << "]"; }
- 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 << "]"; }
- 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 << "]"; }
- 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 << "]"; }
- TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
- TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
- //STL input *****************************************************************************************************
- TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
- TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
- TT1 inline istream& operator >> (istream& os, vector<T>& v) {
- if (v.size()) for (T& t : v) os >> t; else {
- string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
- stringstream ss(s); while (ss >> obj) v.push_back(obj);
- }
- return os;
- }
- TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
- //Pair magic *****************************************************************************************************
- #define PT1T2 pair<T1, T2>
- TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
- TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
- TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
- TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
- #undef TT1
- #undef TT1T2
- #undef TT1T2T3
- #define FREIN(FILE) freopen(FILE, "rt", stdin)
- #define FREOUT(FILE) freopen(FILE, "wt", stdout)
- template<class T> inline void normmod(T &x, T m) { x %= m; if (x < 0) x += m; }
- 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; }
- template<class T1, class T2, class T3> inline void addmodfast(T1 &x, T2 y, T3 m) { x += y; if (x >= m) x -= m; }
- template<class T1, class T2, class T3> inline void submodfast(T1 &x, T2 y, T3 m) { x -= y; if (x < 0) x += m; }
- #if INTPTR_MAX == INT32_MAX
- 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; }
- #else
- inline ll mulmod(ll x, ll n, ll m){ return __int128(x) * n % m; }
- #endif
- 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; }
- 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; }
- template<class T> inline T gcd(T a, T b) { while (b) { a %= b; T t = a; a = b; b = t; } return a; }
- inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
- template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
- ll gcdex(ll a, ll b, ll& x, ll& y) {
- if (!a) { x = 0; y = 1; return b; }
- ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
- return d;
- }
- template<class T> bool isPrime(T x) { if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
- for (T i = 4; i * i <= x; i += 2) if (x % i == 0) return 0; return 1; }
- bool millerRabin(long long n) {
- if (n <= 1000) return isPrime(n);
- long long s = n - 1; int t = 0; while (s % 2 == 0) s /= 2, ++t;
- for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
- long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
- for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
- return false; nextp:;
- } return true;
- }
- // Useful constants
- //int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431, 1000000123};
- #define INF 1011111111
- #define LLINF 1000111000111000111LL
- #define EPS (double)1e-10
- #define mod 998244353
- #define PI 3.14159265358979323846264
- #define link asaxlajrewqwe
- #define rank wahayawehasdakw
- //*************************************************************************************
- int32_t solve();
- int32_t main() {
- ios_base::sync_with_stdio(0);cin.tie(0);
- #ifdef LOCAL
- FREIN("input.txt");
- // FREOUT("out.txt");
- #endif
- return solve();
- }
- int a[101011];
- const int BS = 1 << 14;
- bool used[BS + 7];
- vector<int> blocks[100000 / BS + 11];
- vector<int> positions[100000 / BS + 13];
- int32_t solve() {
- int n;
- cin >> n;
- std::mt19937 gen;
- auto Rnd = [&](int l, int r) {
- return std::uniform_int_distribution<int>(l, r)(gen);
- };
- for (int i = 0; i < n; ++i) {
- a[i] = Rnd(0, n - 1);
- blocks[a[i] / BS].push_back(a[i] % BS);
- positions[a[i] / BS].push_back(i);
- }
- int q;
- cin >> q;
- long long ans = 0;
- const int K = 40;
- while (q--) {
- int l1 = Rnd(0, n / K);
- int r1 = n / 2 - Rnd(0, n / K);
- int l2 = n / 2 + Rnd(1, n / K);
- int r2 = n - Rnd(1, n / K);
- int res = 0;
- for (int j = 0; j * BS < n; ++j) {
- memset(used, 0, BS);
- auto& b = blocks[j];
- for (pii p : {pii(l1, r1), pii(l2, r2)}) {
- int from = int(lower_bound(positions[j].begin(), positions[j].end(), p.first) - positions[j].begin());
- int to = int(upper_bound(positions[j].begin(), positions[j].end(), p.second) - positions[j].begin());
- auto ptr = b.data() + from;
- int cnt = to - from;
- int c4 = cnt / 4;
- while (c4--) {
- res += used[ptr[0]];
- used[ptr[0]] = 1;
- res += used[ptr[1]];
- used[ptr[1]] = 1;
- res += used[ptr[2]];
- used[ptr[2]] = 1;
- res += used[ptr[3]];
- used[ptr[3]] = 1;
- ptr += 4;
- }
- cnt %= 4;
- while (cnt--) {
- auto x = *ptr++;
- res += used[x];
- used[x] = true;
- }
- }
- }
- ans += r1 - l1 + r2 - l2 + 2 - res;
- }
- cout << ans << endl;
- CURTIME();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement