Submission #253313

#	Time	Username	Problem	Language	Result	Execution time	Memory
253313		Mercenary	Cake 3 (JOI19_cake3)	C++14	100 / 100	1863 ms	13560 KiB

cake3

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;

ll s[maxn * 4];
int cnt[maxn * 4];
ll res = -1e18;
int order[maxn] , id[maxn];
int n , m;
ii a[maxn];

void flip(int x , int l , int r , int pos){
    if(l == r){
        if(cnt[x] == 0)cnt[x] = 1 , s[x] = a[order[l]].second;
        else cnt[x] = 0 , s[x] = 0;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid)flip(x * 2 , l , mid , pos);
    else flip(x * 2 + 1 , mid + 1 , r , pos);
    s[x] = s[x * 2] + s[x * 2 + 1];
    cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}

ll get(int x , int l , int r , int k){
    if(cnt[x] <= k)return s[x];
    if(l == r || k <= 0)return 0;
    ll sum = 0;
    int mid = l + r >> 1;
    sum += get(x * 2 + 1 , mid + 1 , r , min(k , cnt[x * 2 + 1]));
    k -= min(k , cnt[x * 2 + 1]);
    sum += get(x * 2 , l , mid , k);
    return sum;
}

void flip(int pos){flip(1,1,n,pos);}
ll get(int k){return get(1,1,n,k);};

int L = 1 , R = 0;

void correct(int l , int r){
    while(L < l)flip(id[L++]);
    while(L > l)flip(id[--L]);
    while(R < r)flip(id[++R]);
    while(R > r)flip(id[R--]);
}

void solve(int l , int r , int bl , int br){
    if(l > r)return;
    int mid = l + r >> 1;
    pair<ll,int> b = mp(-1e18,mid);
    for(int i = bl ; i + m - 1 <= mid && i <= br ; ++i){
        correct(i , mid);
        b = max(b , mp(get(1,1,n,m) - (a[mid].first - a[i].first) * 2 , i));
    }
    res = max(res , b.first);
    solve(l , mid - 1 , bl , b.second);
    solve(mid + 1 , r , b.second , br);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].second >> a[i].first;
    }
    sort(a + 1 , a + n + 1);
    iota(order + 1 , order + n + 1 , 1);
    sort(order + 1 , order + n + 1 , [&](const int x , const int y){
        return a[x].second < a[y].second;
         });
    for(int i = 1 ; i <= n ; ++i){
        id[order[i]] = i;
    }
//    for(int i = 1 ; i <= n ; ++i)cout << id[i] << " ";
    solve(m , n , 1 , n);
    cout << res;
}

Compilation message (stderr)

cake3.cpp: In function 'void flip(int, int, int, int)':
cake3.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'll get(int, int, int, int)':
cake3.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:80:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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