Submission #494586

#	Time	Username	Problem	Language	Result	Execution time	Memory
494586		cadmiumsky	Santa Claus (RMI19_santa)	C++14	90 / 100	711 ms	12188 KiB

santa

#include <iostream>
#include <set>
#include <cstring>
#define int long long
using namespace std;
const int nmax=96068;

int n;

namespace AINT {
  int lazy[nmax * 4], aint[nmax * 4];
  void apply(int node, int cl, int cr) {
    if(cl != cr) {
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    aint[node] += lazy[node];
    lazy[node] = 0;
  }
  void prop(int node, int cl, int cr) {
    int mid = cl + cr >> 1;
    apply(node,cl,cr);
    if(cl != cr) {
      apply(2 * node, cl, mid);
      apply(2 * node, mid + 1, cr);
    }
  }
  void update(int l, int r, int val, int node = 1, int cl = 1, int cr = n) {
    if(l <= cl && cr <= r) {
      //cerr << l <<' '<< r << ' '<< val <<' '<< node << ' '<< cl << ' '<< cr << '\n';
      lazy[node] += val;
      prop(node, cl, cr);
      return;
    }
    prop(node, cl, cr); 
    int mid = cl + cr >> 1;
    if(l <= mid)
      update(l, r, val, node*2, cl, mid);
    if(mid < r)
      update(l, r, val, node * 2 + 1, mid + 1, cr);
    aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
    return;
  } 
  bool query() {
    return aint[1] <= 0;
  }
};

int x[nmax];
int rez[nmax];
int h[nmax];
int v[nmax];

static void testcase() {
  int cnt = 0;
  memset(AINT::lazy,0,sizeof(AINT::lazy));
  memset(AINT::aint,0,sizeof(AINT::aint));
  int ptr=0;
  cin >> n;
  
  for(int i = 0; i < n; i++) {
    cin >> x[i];
    rez[i] = -1;
  }
  for(int i = 0; i < n; i++) {
    cin >> h[i];
    cnt += 1 - h[i];
    if(h[i] == 0)
      ptr = i;
  }
  for(int i = 0; i < n; i++) {
    cin >> v[i];
  }
  multiset<int> appear;
  auto update = [&](int a) {
    AINT::update(v[a], n, h[a] * -2 + 1);
  };
  for(int i = 0; i <= ptr; i++) {
    update(i);
  }
  
  
  for(int force = 0; force < n; force++) {
    if(force > ptr)
      update(++ptr);
    while( !AINT::query() && ptr < n - 1 ) {
      update(++ptr);
    }
    //cout << AINT::query() <<' '<< force+1 << ' '<< ptr+1 << '\n';
    if(AINT::query())
      rez[ptr] = force;
    if(h[force]) {
      auto it = appear.lower_bound(v[force]);
      if(it == appear.end())
        h[force] ^= 1,update(force);
      else {
        //cout << *it <<  ' ' << v[force] <<'\n';
        AINT::update(*it, n, -1);
        AINT::update(v[force], n, 1);
        appear.erase(it);
      }
    }
    else
      appear.insert(v[force]);
  }
  cout << "-1 ";
  for(int i = 1; i < n; i++) {
    rez[i]=max(rez[i-1],rez[i]);
    //cout << rez[i] <<' ';
    if(rez[i] == -1)
      cout << "-1 ";
    else
      cout << x[i]*2 - x[rez[i]] << ' ';
  }
  cout << '\n';
}

signed main() {
  int t;
  cin >> t;
  while(t--) {
    testcase();
  }
}

Compilation message (stderr)

santa.cpp: In function 'void AINT::prop(long long int, long long int, long long int)':
santa.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
santa.cpp: In function 'void AINT::update(long long int, long long int, long long int, long long int, long long int, long long int)':
santa.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

• Subtask 1: 90 / 100