daily pastebin goal
89%
SHARE
TWEET

Untitled

a guest Jan 17th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx")
  3.  
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <algorithm>
  7. #include <assert.h>
  8. #include <immintrin.h>
  9.  
  10. namespace Solution {
  11.    
  12.     const int NMAX = 100000;
  13.  
  14.     const int blockSize = 1024;
  15.    
  16.     const int MaxNBlocks = (NMAX + blockSize - 1) / blockSize;
  17.  
  18.     float* cntTillBorder[MaxNBlocks];
  19.    
  20.     float* zeroBuffer;
  21.    
  22.     float* arr;
  23.    
  24.     int n, nBlocks;
  25.    
  26.     void alloc(int n_) {
  27.         n = n_;
  28.         nBlocks = (n + blockSize - 1) / blockSize;
  29.         arr = (float*)_mm_malloc(n * sizeof(float), 32);
  30.         zeroBuffer = (float*)_mm_malloc(n * sizeof(float), 32);
  31.         std::fill(zeroBuffer, zeroBuffer+n, 0);
  32.         for (int i = 0; i < nBlocks; ++i) {
  33.             cntTillBorder[i] = (float*)_mm_malloc(n * sizeof(float), 32);
  34.             std::fill(cntTillBorder[i], cntTillBorder[i]+n, 0);
  35.         }
  36.     }
  37.    
  38.     void free() {
  39.         _mm_free(arr);
  40.         for (int i = 0; i < nBlocks; ++i) {
  41.             _mm_free(cntTillBorder[i]);
  42.         }
  43.     }
  44.  
  45.     void precalc() {
  46.         for (int i = 0; i < n; ++i) {
  47.             int value = (int)arr[i];
  48.             for (int b = i / blockSize; b < nBlocks; ++b) {
  49.                 cntTillBorder[b][value]++;
  50.             }
  51.         }
  52.     }
  53.    
  54.     void naiveUpdateItems(int begin, int after, float x, float y) {
  55.         int cnt = 0;
  56.         for (int i = begin; i < after; ++i) {
  57.             cnt += (arr[i] == x);
  58.             arr[i] = (arr[i] == x) ? y : arr[i];
  59.         }
  60.         for (int b = begin / blockSize; b < nBlocks; ++b) {
  61.             cntTillBorder[b][int(x)] -= (float)cnt;
  62.             cntTillBorder[b][int(y)] += (float)cnt;
  63.         }
  64.     }
  65.    
  66.     void modify(int lt, int rt, float x, float y) {
  67.         int bl = lt / blockSize;
  68.         int br = rt / blockSize;
  69.         if (bl == br) {
  70.             naiveUpdateItems(lt, rt+1, x, y);
  71.             return;
  72.         }
  73.         int changes = 0;
  74.         for (int i = lt; i < (bl+1) * blockSize; ++i) {
  75.             changes += (arr[i] == x);
  76.             arr[i] = (arr[i] == x) ? y : arr[i];
  77.         }
  78.         cntTillBorder[bl][int(x)] -= (float)changes;
  79.         cntTillBorder[bl][int(y)] += (float)changes;
  80.        
  81.         __m256 vx = _mm256_set1_ps(x);
  82.         __m256 vy = _mm256_set1_ps(y);
  83.        
  84.         for (int b = bl+1; b < br; ++b) {
  85.             float *blockBegin = arr + b * blockSize;
  86.             for (int i = 0; i + 31 < blockSize; i += 32) {
  87.                 uint32_t bitmask = 0;
  88.                 for (int j = 0; j < 32; j += 8) {
  89.                     __m256 va = _mm256_load_ps(blockBegin + i + j);
  90.                     __m256 rs = _mm256_cmp_ps(vx, va, _CMP_EQ_OQ);
  91.                     bitmask = (bitmask << 8) | _mm256_movemask_ps(rs);
  92.                     _mm256_maskstore_ps(blockBegin + i + j, _mm256_cvtps_epi32(rs), vy);
  93.                 }
  94.                 changes += __builtin_popcountll(bitmask);
  95.             }
  96.             cntTillBorder[b][int(x)] -= (float)changes;
  97.             cntTillBorder[b][int(y)] += (float)changes;
  98.         }
  99.        
  100.         for (int i = br * blockSize; i <= rt; ++i) {
  101.             changes += (arr[i] == x);
  102.             arr[i] = (arr[i] == x) ? y : arr[i];
  103.         }
  104.         for (int b = br; b < nBlocks; ++b) {
  105.             cntTillBorder[b][int(x)] -= (float)changes;
  106.             cntTillBorder[b][int(y)] += (float)changes;
  107.         }
  108.        
  109.     }
  110.  
  111.     int nth_element(int lt, int rt, int k) {
  112.         int bl = lt / blockSize;
  113.         int br = rt / blockSize;
  114.         float* arrLT = (bl == 0) ? zeroBuffer : cntTillBorder[bl-1];
  115.         float* arrRT = cntTillBorder[br];
  116.         for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT[(int)arr[i]]--; }
  117.         for (int i = bl * blockSize; i < lt; ++i) { arrLT[(int)arr[i]]++; }
  118.         int last = -1;
  119.         static const int STEP = 32;
  120.         for (int i = 0; i + STEP - 1 < n; i += STEP) {
  121.             _mm_prefetch(arrLT + std::min(i + 2048, n), _MM_HINT_T0);
  122.             _mm_prefetch(arrRT + std::min(i + 2048, n), _MM_HINT_T0);
  123.             __m256 sum = _mm256_setzero_ps(), vr, vl;
  124.             for (int j = 0; j < STEP; j += 8) {
  125.                 vr = _mm256_load_ps(arrRT+i+j);
  126.                 vl = _mm256_load_ps(arrLT+i+j);
  127.                 sum = _mm256_add_ps(sum, _mm256_sub_ps(vr, vl));
  128.             }
  129.             alignas(32) static float tmp[8];
  130.             _mm256_store_ps(tmp, sum);
  131.             int cnt = 0;
  132.             for (int j = 0; j < 8; ++j) { cnt += (int)tmp[j]; }
  133.             if (cnt >= k) { last = i-1; break; }
  134.             k -= cnt;
  135.             last = i + STEP - 1;
  136.         }
  137.         int cnt = 0;
  138.         while (cnt < k) { last++; cnt += int(arrRT[last] - arrLT[last]); }
  139.         for (int i = bl * blockSize; i < lt; ++i) { arrLT[(int)arr[i]]--; }
  140.         for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT[(int)arr[i]]++; }
  141.         return last;
  142.     }
  143. }
  144.  
  145. char getChar() {
  146.     static const int SIZE = 1 << 16;
  147.     static char buffer[SIZE];
  148.     static int pos = 0;
  149.     static int size = 0;
  150.     if (pos == size) {
  151.         size = (int)fread(buffer, 1, SIZE, stdin),
  152.         pos = 0;
  153.     }
  154.     if (pos == size) {
  155.         return EOF;
  156.     }
  157.     return buffer[pos++];
  158. }
  159.  
  160. template<typename T>
  161. T getInt() {
  162.     char c = '?';
  163.     while (!(c == '-' || ('0' <= c && c <= '9'))) { c = getChar(); }
  164.     bool pos = true;
  165.     if (c == '-') { pos = false; c = getChar(); }
  166.     T ret = 0;
  167.     while ('0' <= c && c <= '9') { (ret *= 10) += (c - '0'); c = getChar(); }
  168.     return pos ? ret : -ret;
  169. }
  170.  
  171. void putChar(char c) {
  172.     static const int SIZE = 1 << 16;
  173.     static char buffer[SIZE];
  174.     static int size = 0;
  175.     if (size == SIZE || c == EOF) {
  176.         fwrite(buffer, 1, size, stdout),
  177.         size = 0;
  178.     }
  179.     if (c != EOF) { buffer[size++] = c; }
  180. }
  181.  
  182. template<typename T>
  183. void putInt(T value) {
  184.     bool pos = true;
  185.     if (value < 0) { pos = false; value = -value; }
  186.     static char buf[24];
  187.     int size = 0;
  188.     do { buf[size++] = char(value % 10 + '0'); value /= 10; } while (value > 0);
  189.     if (!pos) { buf[size++] = '-'; }
  190.     while (size--) { putChar(buf[size]); }
  191. }
  192.  
  193. #include <random>
  194.  
  195. void stress() {
  196.     int n = 100000, q = 100000;
  197.     Solution::alloc(n);
  198.     for (int i = 0; i < n; ++i) {
  199.         Solution::arr[i] = float(n-1);
  200.     }
  201.     Solution::precalc();
  202.     std::mt19937 gen;
  203.     std::uniform_int_distribution<int> dist(0, n-1);
  204.     int last = n-1;
  205.     uint64_t sum = 0;
  206.     for (int id = 0; id < q; ++id) {
  207.         if (id % 2 == 0) {
  208.             int l = dist(gen);
  209.             int r = dist(gen);
  210.             if (l > r) { std::swap(l, r); }            
  211.             auto res = Solution::nth_element(l, r, (r-l+1));
  212.             assert(res == last);
  213.             sum += res;
  214.         } else {
  215.             int x = last;
  216.             int y = (n-1) + (n-2) - last;
  217.             Solution::modify(0, n-1, x, y);
  218.             last = y;
  219.         }
  220.     }
  221.     assert(sum != 0);
  222.     Solution::free();
  223.     std::exit(0);
  224. }
  225.  
  226. int main() {
  227.     //stress();
  228.     int n = getInt<int>(), q = getInt<int>();
  229.     Solution::alloc(n);
  230.     for (int i = 0; i < n; ++i) {
  231.         Solution::arr[i] = (float)(getInt<int>()-1);
  232.     }
  233.     Solution::precalc();
  234.    
  235.     while (q--) {
  236.         int t = getInt<int>();
  237.         if (t == 1) {
  238.             int lt = getInt<int>()-1, rt = getInt<int>()-1, x = getInt<int>()-1, y = getInt<int>()-1;
  239.             Solution::modify(lt, rt, (float)x, (float)y);
  240.         } else {
  241.             int lt = getInt<int>()-1, rt = getInt<int>()-1, k = getInt<int>();
  242.             putInt(Solution::nth_element(lt, rt, k)+1);
  243.             putChar('\n');
  244.             assert(t == 2);
  245.         }
  246.     }
  247.     putChar(EOF);
  248.     Solution::free();
  249.     return 0;
  250. }
RAW Paste Data
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
 
Top