Submission #531474

#	Time	Username	Problem	Language	Result	Execution time	Memory
531474		cadmiumsky	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4541 ms	114096 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

const int nmax = 1e6 + 3; // e memorie putina, nu merge +5

int len;

namespace AINT {
  int lazy[4 * nmax];
  int maxx[4 * nmax];
  namespace AIB {
    #define lsb(x) (x & (-x))
    int active[nmax];
    int sum[nmax];
    void upd(int x, int val) {
      while(x <= len)
        sum[x] += val, x += lsb(x);
    }
    int query(int x) {
      int s = 0;
      while(x > 0)
        s += sum[x], x -= lsb(x); 
      return s;
    }
    void toggle(int poz) {
      upd(poz, (active[poz] ^ 1) - active[poz]);
      active[poz] ^= 1;
    }
  }
  void apply(int node, int cl, int cr) {
    maxx[node] += lazy[node];
    int mid = cl + cr >> 1;
    if(cl != cr)
      lazy[2 * node] += lazy[node], lazy [2 * node + 1] += lazy[node];
    lazy[node] = 0;
  }
  void prop(int node, int cl, int cr) {
    apply(node, cl, cr);
    int mid = cl + cr >> 1;
    if(cl != cr) {
      apply(2 * node, cl, mid);
      apply(2 * node + 1, mid + 1, cr);
    }
    return;
  }
  void push(int poz, int val, int node = 1, int cl = 1, int cr = len) {
    //cerr << poz << ' ' << cl << ' ' << cr << '\n';
    prop(node, cl, cr);
    if(cl == cr) {
      maxx[node] = val;
      return;
    }
    int mid = cl + cr >> 1;
    if(poz <= mid)
      push(poz, val, 2 * node, cl, mid);
    else
      push(poz, val, 2 * node + 1, mid + 1, cr);
    maxx[node] = max(maxx[2 * node], maxx[2 * node + 1]);
    return;
  }
  void add(int l, int r, int val = 1, int node = 1, int cl = 1, int cr = len) {
    prop(node, cl, cr);
    #warning incearca cu apply simplu
    if(r < cl || cr < l)
      return;
    if(l <= cl && cr <= r) {
      lazy[node] += val;
      prop(node, cl, cr);
      return;
    }
    int mid = cl + cr >> 1;
    add(l, r, val, 2 * node, cl, mid);
    add(l, r, val, 2 * node + 1, mid + 1, cr);
    maxx[node] = max(maxx[2 * node], maxx[2 * node + 1]);
  }
  void erase(int poz) {
    AIB::toggle(poz);
    push(poz, - 2e6 - 5);
    add(poz + 1, len);
  }
  void insert(int poz, int val) {
    push(poz, val - AIB::query(poz));
    add(poz + 1, len, -1);
    AIB::toggle(poz);
  }
  void construct(int node = 1, int cl = 1, int cr = len) {
    maxx[node] = -2e6 - 5;
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    construct(2 * node, cl, mid);
    construct(2 * node + 1, mid + 1, cr);
    return;
  }
}
namespace NORM {
  map<pair<int,int>, int> norm;
  void push(int v, int poz) {
    norm[{v, poz}];
  }
  void init() {
    int cnt = 1;
    for(auto &x : norm) 
      x.second = cnt++; 
    len = norm.size() + 1;
  }
  int query(int v, int poz) {
    return norm[{v, poz}];
  }
};

vector<int> countScans(vector<int> a, vector<int> x, vector<int> y){
  int n = a.size(), q = x.size();
  vector<int> ans(q);
  for(int i = 0; i < n; i++)
    NORM::push(a[i], i);
  for(int i = 0; i < q; i++)
    NORM::push(y[i], x[i]);
  NORM::init();
  AINT::construct();
  for(int i = 0; i < n; i++)
    AINT::insert(NORM::query(a[i], i), i);
  for(int i = 0; i < q; i++) {
    AINT::erase(NORM::query(a[x[i]], x[i]));
    AINT::insert(NORM::query(y[i], x[i]), x[i]);
    a[x[i]] = y[i];
    ans[i] = AINT::maxx[1];
  }
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp:64:6: warning: #warning incearca cu apply simplu [-Wcpp]
   64 |     #warning incearca cu apply simplu
      |      ^~~~~~~
bubblesort2.cpp: In function 'void AINT::apply(int, int, int)':
bubblesort2.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bubblesort2.cpp:33:9: warning: unused variable 'mid' [-Wunused-variable]
   33 |     int mid = cl + cr >> 1;
      |         ^~~
bubblesort2.cpp: In function 'void AINT::prop(int, int, int)':
bubblesort2.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bubblesort2.cpp: In function 'void AINT::push(int, int, int, int, int)':
bubblesort2.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bubblesort2.cpp: In function 'void AINT::add(int, int, int, int, int, int)':
bubblesort2.cpp:72:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
bubblesort2.cpp: In function 'void AINT::construct(int, int, int)':
bubblesort2.cpp:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40