oj.uz

답안 #345120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345120 2021-01-07T04:16:34 Z casperwang 쌀 창고 (IOI11_ricehub) C++14
0 / 100
 288 ms 1488 KB 
#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);
    }
    long long 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 = 1;
  seg.build();
  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;
    }
    ans = max(ans, solve(nowL, B));
    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

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 'long long 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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 1488 KB Output isn't correct
2 Halted 0 ms 0 KB -