Submission #447697

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
447697	2021-07-27 10:59:53	dutch	Cake 3 (JOI19_cake3)	C++17	100 / 100	553 ms	15048 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int LIM = 2e5, INF = 1e18;
int n, m, L, R, fVal[LIM+1], fCnt[LIM+1], pos[LIM], ans = -INF;
array<int, 2> a[LIM], b[LIM];
void add(int i, int j){
  int v = a[i][1] * j; i = pos[i];
  for(; i<=n; i+=i&-i){
    fCnt[i] += j;
    fVal[i] += v;
  }
}
int get(int l, int r){
  assert(r-l >= m-2);
  while(R < r) add(R++, 1);
  while(L > l) add(--L, 1);
  while(R > r) add(--R,-1);
  while(L < l) add(L++,-1);
  int v = m - 2, i = 0, s = 0;
  for(int j=1<<19; j/=2; ){
    if(i+j <= n && fCnt[i+j] <= v){
      i += j;
      s += fVal[i];
      v -= fCnt[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76