Submission #363443

#	Time	Username	Problem	Language	Result	Execution time	Memory
363443		Killer2501	Cake 3 (JOI19_cake3)	C++14	100 / 100	3989 ms	18164 KiB

cake3

//#include "holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<vector<ll>, ll>
#define fi first
#define se second
using ll = int;
const long long mod = 1e16+7;
const ll mod1 = 1e9+1;
const ll N = 2e5+5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, u, v, a[N], c[N], d[N], b[N],  cnt[N*4], s;
long long ans, tong, sum[N*4];
vector<ll> adj[N], kq;
vector<pll> l, r;
pll p[N];
void update(ll id, ll l, ll r, ll pos)
{
    if(l == r)
    {
        if(cnt[id] == 0)
        {
            cnt[id] = 1;
            sum[id] = p[c[l]].se;
        }
        else
        {
            cnt[id] = 0;
            sum[id] = 0;
        }
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= pos)update(id*2, l, mid, pos);
    else update(id*2+1, mid+1, r, pos);
    sum[id] = sum[id*2] + sum[id*2+1];
    cnt[id] = cnt[id*2] + cnt[id*2+1];
}
long long get(ll id, ll l, ll r, ll k)
{
    //if(t == 1)cout << l <<" "<<r<<" "<<k<<" "<<sum[id]<<" " << cnt[id] <<" "<<cnt[id*2]<< '\n';
    if(cnt[id] <= k)return sum[id];
    if(k == 0 || l == r)return 0;
    if(k < 0)return -mod;
    ll mid = (l + r) / 2;
    if(cnt[id*2] >= k)return get(id*2, l, mid, k);
    else return sum[id*2] + get(id*2+1, mid+1, r, k-cnt[id*2]);
}

void add(ll cl, ll cr)
{
    while(u < cl)
    {
        update(1, 1, n, b[u]);
        ++u;
    }
    while(u > cl)
    {
        --u;
        update(1, 1, n, b[u]);
    }
    while(v < cr)
    {
        ++v;
        update(1, 1, n, b[v]);
    }
    while(v > cr)
    {
        update(1, 1, n, b[v]);
        --v;
    }
}
void cal(ll l, ll r, ll opl, ll opr)
{
    if(l > r)return;
    ll mid = (l + r) / 2;
    ll best = opl;
    long long val = -mod;
    for(int i = opl; i <= min(mid-m+1, opr); i ++)
    {
        add(i, mid);
        if(mid - i + 1 >= m)
        {
            update(1, 1, n, b[i]);
            update(1, 1, n, b[mid]);
            tong = get(1, 1, n, m-2);
            //cout << i <<" "<<mid<<" "<<tong<<'\n';
            tong += p[i].se + p[mid].se - 2*(p[mid].fi - p[i].fi);
            update(1, 1, n, b[i]);
            update(1, 1, n, b[mid]);
        }
        else tong = -mod;
        if(tong > val)
        {
            val = tong;
            best = i;
        }
        //cout << "ok" <<" ";
    }
    //cout << l <<" "<<r<<" "<<mid<<" "<<opl<< " "<<opr<<" "<<val<<endl;
    //cout << l <<" "<< r << " " << mid << endl;;
    ans = max(ans, val);
    cal(l, mid-1, opl, best);
    cal(mid+1, r, best, opr);
}
bool cmp(const ll& x, const ll& y)
{
    return p[x].se > p[y].se;
}
void sol()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> p[i].se >> p[i].fi;
        c[i] = i;
    }
    ans = -mod;
    u = 2, v = 1;
    sort(p+1, p+1+n);
    sort(c+1, c+1+n, cmp);
    for(int i = 1; i <= n; i ++)b[c[i]] = i;
    //for(int i = 1; i <= n; i ++)cout << b[i] <<" " ;
    cal(1, n, 1, n);
    cout <<  ans;
}

int main()
{
    if(fopen(task".in", "r")){
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest;
    ntest =  1;
    //cin >> ntest;
    //cout << (1<<30) << '\n';
    while(ntest -- > 0)
    sol();

}
/*
5 7 3
10 2 20 30 1
*/

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:135:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  135 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:136:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  136 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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