Submission #345118

#	Time	Username	Problem	Language	Result	Execution time	Memory
345118		casperwang	Rice Hub (IOI11_ricehub)	C++14	0 / 100	288 ms	1516 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 200000;
int _R;
int ans;

class Seg{
  private:
    long long arr[MAXN*4+5];
    long long tag[MAXN*4+5];
    void pull(int now) {
      arr[now] = arr[now*2] + arr[now*2+1];
    }
    void push(int now, int len) {
      if (!tag[now]) return;
      arr[now] += tag[now] * len;
      if (len > 1) {
        tag[now*2  ] += tag[now];
        tag[now*2+1] += tag[now];
      }
      tag[now] = 0;
    }
  public:
    void build(int now=1, int l=0, int r=_R-1) {
      if (l == r) {
        arr[now] = tag[now] = 0;
        return;
      }
      int mid = l + r >> 1;
      build(now*2  , l, mid);
      build(now*2+1,mid+1,r);
      pull(now);
    }
    void mdy(int ml, int mr, int v, int now=1, int l=0, int r=_R-1) {
      push(now, r-l+1);
      if (ml <= l && r <= mr) {
        tag[now] += v;
        push(now, r-l+1);
        return;
      } else if (l > mr || r < ml) return;
      int mid = l + r >> 1;
      mdy(ml, mr, v, now*2  , l, mid);
      mdy(ml, mr, v, now*2+1,mid+1,r);
      pull(now);
    }
    int qry(int ql, int qr, int now=1, int l=0, int r=_R-1) {
      push(now, r-l+1);
      if (ql <= l && r <= qr) {
        return arr[now];
      } else if (l > qr || r < ql) return 0;
      int mid = l + r >> 1;
      long long sum = 0;
      sum += qry(ql, qr, now*2  , l, mid);
      sum += qry(ql, qr, now*2+1,mid+1,r);
      pull(now);
      return sum;
    }
} seg;

int solve(int p, long long B) {
  int l = p, r = _R-1, mid;
  while (l < r) {
    mid = (l + r + 1) >> 1;
    if (seg.qry(p, mid) <= B)
      l = mid;
    else
      r = mid - 1;
  }
  return l - p + 1;
}

int besthub(int R, int L, int X[], long long B) {
  _R = R;
  ans = 0;
  seg.build(1, 0, R-1);
  for (int i = 1; i < R; i++)
    seg.mdy(i, i, X[i] - X[0]);
  int nowL = 0;
  for (int i = 0; i < R; i++) {
    int v = solve(nowL, B);
    while (nowL < i) {
      if (solve(nowL+1, B) >= v)
        nowL++;
      else
        break;
    }
    int tmp = solve(nowL, B);
    if (tmp > ans) ans = tmp;
    if (i+1 < R) {
      seg.mdy(0, i, X[i+1] - X[i]);
      seg.mdy(i+1, R-1, X[i] - X[i+1]);
    }
  }
  return ans;
}

Compilation message (stderr)

ricehub.cpp: In member function 'void Seg::build(int, int, int)':
ricehub.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |       int mid = l + r >> 1;
      |                 ~~^~~
ricehub.cpp: In member function 'void Seg::mdy(int, int, int, int, int, int)':
ricehub.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = l + r >> 1;
      |                 ~~^~~
ricehub.cpp: In member function 'int Seg::qry(int, int, int, int, int)':
ricehub.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32