Submission #1022249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022249		NeroZein	Distributing Candies (IOI21_candies)	C++17	29 / 100	213 ms	20076 KiB

candies

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

const int N = 2e5 + 5;

struct node {
  int mn = 0, mx = 0;
  int lazy_add = 0, lazy_set = -1; 
};

node seg[N * 2];
pair<int, int> c[N];

node merge(node lx, node rx) {
  node ret;
  ret.mn = min(lx.mn, rx.mn);
  ret.mx = max(lx.mx, rx.mx); 
  return ret;
}

void push(int nd, int l, int r) {
  if (seg[nd].lazy_set != -1) {
    //cout << "push: " << l << ' ' << r << ' ' << seg[nd].lazy_set << '\n';
    if (seg[nd].lazy_set == 0) {
      seg[nd].mn = seg[nd].mx = 0;
    } else {
      seg[nd].mn = c[l].first;
      seg[nd].mx = c[r].first; 
    }
    if (l != r) {
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      seg[nd + 1].lazy_set = seg[nd].lazy_set;
      seg[rs].lazy_set = seg[nd].lazy_set;
      seg[nd + 1].lazy_add = seg[rs].lazy_add = 0;
    }
    seg[nd].lazy_set = -1; 
  }
  seg[nd].mn += seg[nd].lazy_add;
  seg[nd].mx += seg[nd].lazy_add;
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    seg[nd + 1].lazy_add += seg[nd].lazy_add;
    seg[rs].lazy_add += seg[nd].lazy_add;
  }
  seg[nd].lazy_add = 0;
}

void upd(int nd, int l, int r, int v) {
  push(nd, l, r);
  if (l == r) {
    //cout << "l, v: " << l << ' ' << v << endl; 
    seg[nd].mx = max(0, seg[nd].mx + v);
    seg[nd].mn = max(0, seg[nd].mn + v);
    seg[nd].mx = min(seg[nd].mx, c[l].first);
    seg[nd].mn = min(seg[nd].mn, c[l].first);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  push(nd + 1, l, mid);
  if (seg[nd + 1].mx + v <= 0) {
    seg[nd + 1].lazy_add = 0;
    seg[nd + 1].lazy_set = 0; 
    upd(rs, mid + 1, r, v); 
  } else if (seg[nd + 1].mx + v >= c[mid].first) {
    seg[nd + 1].lazy_add = 0;
    seg[nd + 1].lazy_set = 1; 
    //if (v == 1) {
      //cout << "Q: " << l << ' ' << r << ' ' << seg[nd + 1].mx << '\n'; 
    //}
    upd(rs, mid + 1, r, v); 
  } else {
    seg[rs].lazy_add += v;
    upd(nd + 1, l, mid, v); 
  }
  push(nd + 1, l, mid);
  push(rs, mid + 1, r); 
  seg[nd] = merge(seg[nd + 1], seg[rs]);
}

int qry(int nd, int l, int r, int p) {
  push(nd, l, r); 
  if (l == r) {
    assert(seg[nd].mn == seg[nd].mx);
    return seg[nd].mn;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    return qry(nd + 1, l, mid, p);
  }
  return qry(rs, mid + 1, r, p); 
}
 
vector<int> distribute_candies(vector<int> c_, vector<int> ql, vector<int> qr, vector<int> v) {
  int n = (int) c_.size();
  int q = (int) ql.size(); 
  for (int i = 0; i < n; ++i) {
    c[i].first = c_[i];
    c[i].second = i; 
  }
  sort(c, c + n);
  for (int i = 0; i < q; ++i) {
    upd(0, 0, n - 1, v[i]);
    //cout << "ARR: ";
    //for (int j = 0; j < n; ++j) {
      //cout << qry(0, 0, n - 1, j) << ' ';
    //}
    //cout << '\n';
  }
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    s[c[i].second] = qry(0, 0, n - 1, i);
  }
  return s;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33