Submission #203585

#	Time	Username	Problem	Language	Result	Execution time	Memory
203585		theStaticMind	Cake 3 (JOI19_cake3)	C++14	100 / 100	842 ms	110864 KiB

cake3

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000ll
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;
 
struct Node{
      int left, right;
      long long int sum;
      int cnt;
      void set(int a, int b, int c, int d, long long int e, int f){
            left = a;
            right = b;
            sum = e;
            cnt = f;
      }
      Node(){}
};
 
Node seg[8000000];
vector<int> root(200005);
vector<ii> arr;
vector<ii> util;
vector<int> ptr(200005);
int ind = 0;
int S;
 
int new_node(){
      return ind++;
}
 
long long int getsum(int i, int j){
      return seg[j].sum - seg[i].sum;
}
int getcnt(int i, int j){
      return seg[j].cnt - seg[i].cnt;
}
 
void build(int curr, int l, int r){
      if(r == l){
            seg[curr].set(-1, -1, l, r, 0, 0);
            return;
      }
      seg[curr].set(new_node(), new_node(), l, r, 0, 0);
 
      build(seg[curr].left, l, (l + r) / 2);
      build(seg[curr].right, (l + r) / 2 + 1, r);
}
 
int pers(int j, int l, int r, int x){
      int curr = new_node();
      if(l != r){
            int mid = (l + r) / 2;
            int q, w;
            if(x <= mid) {
                  q = pers(seg[j].left ,l, mid, x);
                  w = seg[j].right;
            }
            else{
                  q = seg[j].left;
                  w = pers(seg[j].right ,mid + 1, r, x);
            }
            seg[curr].set(q, w, l, r, seg[q].sum + seg[w].sum, seg[q].cnt + seg[w].cnt);
      }
      else{
            seg[curr].set(-1, -1, l, r, util[l].first, 1);
      }
      return curr;
}
 
long long int query(int j1, int l, int r, int x, int j2){
      if(getcnt(j1, j2) == 0 || x == 0)return 0;
      if(l == r) return getsum(j1, j2);
      int q = seg[j1].left;
      int w = seg[j1].right;
      int Q = seg[j2].left;
      int W = seg[j2].right;
      if(x == getcnt(j1, j2)){
            return getsum(j1, j2);
      }
      if(x <= getcnt(q, Q)){
            return query(q, l, (l + r) / 2, x, Q);
      }
      return getsum(q, Q) + query(w, (l + r) / 2 + 1, r, max(x - getcnt(q, Q), 0), W);
}
void print(int j, int l, int r){
      cout << "("<<l<<","<<r<<") = "<< seg[j].sum << " " << seg[j].cnt << "\n";
      if(l == r){
            return;
      }
      print(seg[j].left, l, (l + r) / 2);
      print(seg[j].right, (l + r) / 2 + 1, r);
}
 
long long int compute(int l, int r, int optl, int optr, int m){
      if(l > r) return -INF;
      int mid = (l + r) / 2;
      long long int w = -INF;
      int opt = optl;
      for(int k = optl; k <= min(optr, mid); k++){
            long long int q = -INF;
            if(mid - k + 1 >= m){
                  q = query((k > 0 ? root[k - 1] : 0), 0, S - 1, m - 1, root[mid - 1]) - 2ll * (arr[mid].first - arr[k].first) + 1ll * arr[mid].second;
 
            }
            if(q > w){
                  w = q;
                  opt = k;
            }
      }
      return max(w, max(compute(l, mid - 1, optl, opt, m), compute(mid + 1, r, opt, optr, m)));
}
 
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
  
      int n, m;
      cin >> n >> m;
 
      for(int i = 0; i < n; i++){
            int x, y;
            cin >> x >> y;
            arr.pb({y, x});
      }
      sort(all(arr));
      for(int i = 0; i < n; i++){
            util.pb({arr[i].second, i});
      }
      sort(all(util), greater<ii>());
      for(int i = 0; i < n; i++) ptr[util[i].second] = i;
 
      S = (1 << (int)ceil(log2(n)));
      build(new_node(), 0, S - 1);
 
      for(int i = 0; i < n; i++){
            root[i] = pers((i > 0 ? root[i - 1] : 0), 0, S - 1, ptr[i]);
      }
      cout << compute(0, n - 1, 0, n - 1, m);
}

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