제출 #202429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202429		Rakhmand	Cake 3 (JOI19_cake3)	C++14	24 / 100	515 ms	262148 KiB

cake3

//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
 
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
 
const long long MXN = 1e6 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e16;
const long long OO = 1e9 + 10;
 
typedef long long llong;
typedef unsigned long long ullong;
 
using namespace std;
 
void istxt(bool yes){
    if(yes == 1){
        freopen("balancing.in", "r", stdin);
        freopen("balancing.out", "w", stdout);
    }else{
        freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
    }
}
 
llong n, m;
llong answer = -INF;
pair<int, int> p[MXN];
vector<int> c;
 
int find_pos(int x) { return (lower_bound(c.begin(), c.end(), x) - c.begin()); }
 
struct node{
    node *l, *r;
    int cnt;
    llong sum;
    node(){
        l = r = nullptr;
        cnt = sum = 0;
    }
};
typedef node* pnode;
pnode t[MXN];
 
int getcnt(pnode x) {return (x == nullptr ? 0 : x -> cnt); }
llong getsum(pnode x) { return (x == nullptr ? 0 : x -> sum); }
 
 
pnode upd(pnode last, llong pos, llong tl = 0, llong tr = c.size() - 1){
    pnode cur = new node();
    if(tl == tr){
        cur -> sum = getsum(last) + c[pos];
        cur -> cnt = getcnt(last) + 1;
        return cur;
    }
    llong tm = (tl + tr) / 2;
    if(pos <= tm){
        cur -> l = new node();
        if(last != nullptr){
            cur -> l = upd(last -> l, pos, tl, tm);
            cur -> r = last -> r;
        }else{
            cur -> l = upd(nullptr, pos, tl, tm);
            cur -> r = nullptr;
        }
    }else{
        cur -> r = new node();
        if(last != nullptr){
            cur -> l = last -> l;
            cur -> r = upd(last -> r, pos, tm + 1, tr);
        }else{
            cur -> l = nullptr;
            cur -> r = upd(nullptr, pos, tm + 1, tr);
        }
    }
    cur -> sum = getsum(cur->l) + getsum(cur->r);
    cur -> cnt = getcnt(cur->l) + getcnt(cur->r);
    return cur;
}
 
llong get(pnode v, pnode last, llong k, llong tl = 0, llong tr = c.size() - 1){
    if(k == 0) return 0;
    if(tl == tr) {
        if(v == nullptr) return 0;
        llong x = v -> sum / v -> cnt;
        return x * k;
    }
    llong right = 0;
    if(v != nullptr) right = getcnt(v -> r);
    if(last != nullptr) right -= getcnt(last -> r);
    llong tm = (tl + tr) / 2;
    if(right < k){
        llong sum = 0;
        if(v != nullptr) sum += getsum(v -> r);
        if(last != nullptr) sum -= getsum(last -> r);
        return sum + get((v == nullptr ? nullptr : v -> l), (last == nullptr ? nullptr : last -> l), k - right, tl, tm);
    }else{
        return get((v == nullptr ? nullptr : v -> r), (last == nullptr ? nullptr : last -> r), k, tm + 1, tr);
    }
}

void f(llong L, llong R, llong optl, llong optr){
    llong M = (L + R) / 2;
    llong ans = -INF, pos = -1;
    for(llong i = max(M, optl); i <= optr; i++){
        llong kek = get(t[i], t[M - m], m) - 2 * (p[i].F - p[M - m + 1].F);
        if(kek > ans){
            ans = kek;
            pos = i;
        }
    }
    answer = max(ans, answer);
    if(M - 1 >= L)
        f(L, M - 1, optl, pos);
    if(M + 1 <= R)
        f(M + 1, R, pos, optr);
}
 
int main () {
    ios;
    //istxt(0);
    cin >> n >> m;
    for(llong i = 1; i <= n; i++){
        cin >> p[i].S >> p[i].F;
        c.push_back(p[i].S);
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    sort(p + 1, p + n + 1);
    t[0] = new node();
    for(llong i = 1; i <= n; i++){
        t[i] = upd(t[i - 1], find_pos(p[i].S));
    }
    f(m, n, m, n);
    cout << answer;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'void istxt(bool)':
cake3.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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