제출 #1082881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082881		phong	Cake 3 (JOI19_cake3)	C++17	100 / 100	1506 ms	33216 KiB

cake3

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 15, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
pii a[nmax];
ll best[nmax];
multiset<pii> one, two;
struct node{
    int l, r, from, to;
};
vector<node> adj[50];
ll pre[nmax], suf[nmax];
int el[nmax];
pii b[nmax];
struct hos{
    int cnt, w;
}tree[nmax << 2];
void update(int id, int l, int r, int u, int idx){
    if(l > u || r < u) return;
    if(l >= u && r <= u){
        if(idx){
            tree[id].cnt = 1;
            tree[id].w = b[l].fi;
            return;
        }
        else {
            tree[id].cnt = 0;
            tree[id].w = 0;
            return;
        }
    }
    int mid= r + l >> 1;
    update(id << 1, l, mid, u, idx);
    update(id << 1 | 1, mid + 1, r, u, idx);
    tree[id].cnt = tree[id << 1].cnt + tree[id << 1 | 1].cnt;
    tree[id].w = tree[id << 1].w + tree[id << 1 | 1].w;
}
int get(int id, int l, int r, int u, int v, int k){
    if(tree[id].cnt <= k) return tree[id].w;
    int mid = r + l >> 1;
    if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v, k);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v, k);
    if(k <= tree[id << 1].cnt) return get(id << 1, l, mid, u, v, k);
    return tree[id << 1].w + get(id << 1 | 1, mid + 1, r, u,v, k - tree[id << 1].cnt);
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + 1 + n, [](pii a, pii b){
        return a.se < b.se;
         });
    for(int i = 1; i <= n; ++i) b[i] = {a[i].fi, i};
    sort(b + 1, b + 1 + n, [](pii a, pii b){
        return a.fi > b.fi;
         });
    for(int i = 1; i <= n; ++i) el[b[i].se] = i;
    pre[0] = suf[n + 1] = -oo;
    for(int i = 1; i <= n; ++i){
        pre[i] = max(pre[i - 1], a[i].fi + 2 * a[i].se);
    }
//    cout << pre[1] << ' ';
    for(int i = n; i >= 1; --i){
        suf[i] = max(suf[i + 1], a[i].fi - 2 * a[i].se);
    }
    adj[1].push_back({1, n, 1, n});
    ll ans = -oo;
    for(int e = 1; e <= 20; ++e){
        if(adj[e].empty()) continue;
        int pos = 1, pre_pos = 1;
        ll cur = 0;
        for(int i = 1; i <= n; ++i) update(1, 1, n, i, 0);
        for(auto [l, r, from, to] : adj[e]){
            int mid = r + l >> 1;
            auto &p = best[mid];
            p = to;
            int ma = -oo;
            for(int i = from; i <= to; ++i){
                if(i - mid + 1 < m) continue;
                while(pos < i){
                    update(1, 1, n, el[pos], 1);
                    ++pos;
                }
                while(pre_pos <= mid){
                    update(1, 1, n, el[pre_pos], 0);
                    ++pre_pos;
                }
                ll res = pre[mid] + suf[i] + get(1, 1, n, 1, n, m - 2);
//                cout << res << ' ';
                if(ma < res){
                    ma = res;
                    p = i;
                    ans = max(ans, ma);
                }
            }
            if(l < mid) adj[e + 1].push_back({l, mid - 1, from, p});
            if(mid < r) adj[e + 1].push_back({mid + 1, r, p, to});
        }
    }
//    debug(best, n);
    cout << ans;
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 3 4


*/

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

cake3.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:44:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid= r + l >> 1;
      |              ~~^~~
cake3.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = r + l >> 1;
      |               ~~^~~
cake3.cpp: At global scope:
cake3.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:90:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |             int mid = r + l >> 1;
      |                       ~~^~~
cake3.cpp:87:12: warning: unused variable 'cur' [-Wunused-variable]
   87 |         ll cur = 0;
      |            ^~~

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