oj.uz

Submission #202429

# Submission time Handle Problem Language Result Execution time Memory
202429 2020-02-16T04:42:25 Z Rakhmand Cake 3 (JOI19_cake3) C++14
24 / 100
 515 ms 262148 KB 
//
//  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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 380 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 6 ms 380 KB Output is correct
35 Correct 6 ms 380 KB Output is correct
36 Correct 5 ms 376 KB Output is correct
37 Correct 5 ms 376 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 380 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 6 ms 380 KB Output is correct
35 Correct 6 ms 380 KB Output is correct
36 Correct 5 ms 376 KB Output is correct
37 Correct 5 ms 376 KB Output is correct
38 Correct 10 ms 2424 KB Output is correct
39 Correct 10 ms 2552 KB Output is correct
40 Correct 9 ms 2424 KB Output is correct
41 Correct 9 ms 2296 KB Output is correct
42 Correct 9 ms 2424 KB Output is correct
43 Correct 8 ms 2296 KB Output is correct
44 Correct 9 ms 2424 KB Output is correct
45 Correct 9 ms 2424 KB Output is correct
46 Correct 9 ms 2552 KB Output is correct
47 Correct 9 ms 2424 KB Output is correct
48 Correct 9 ms 2296 KB Output is correct
49 Correct 9 ms 2552 KB Output is correct
50 Correct 9 ms 2428 KB Output is correct
51 Correct 9 ms 2424 KB Output is correct
52 Correct 8 ms 2424 KB Output is correct
53 Correct 9 ms 2428 KB Output is correct
54 Correct 8 ms 2424 KB Output is correct
55 Correct 8 ms 2424 KB Output is correct
56 Correct 9 ms 2424 KB Output is correct
57 Correct 8 ms 2424 KB Output is correct
58 Correct 8 ms 2424 KB Output is correct
59 Correct 5 ms 504 KB Output is correct
60 Correct 6 ms 632 KB Output is correct
61 Correct 5 ms 504 KB Output is correct
62 Correct 5 ms 504 KB Output is correct
63 Correct 6 ms 632 KB Output is correct
64 Correct 6 ms 504 KB Output is correct
65 Correct 9 ms 2424 KB Output is correct
66 Correct 9 ms 2424 KB Output is correct
67 Correct 9 ms 2424 KB Output is correct
68 Correct 9 ms 2552 KB Output is correct
69 Correct 9 ms 2424 KB Output is correct
70 Correct 8 ms 2424 KB Output is correct
71 Correct 7 ms 1016 KB Output is correct
72 Correct 6 ms 1144 KB Output is correct
73 Correct 9 ms 2424 KB Output is correct
74 Correct 8 ms 2552 KB Output is correct

Subtask #3
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 380 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 6 ms 380 KB Output is correct
35 Correct 6 ms 380 KB Output is correct
36 Correct 5 ms 376 KB Output is correct
37 Correct 5 ms 376 KB Output is correct
38 Correct 10 ms 2424 KB Output is correct
39 Correct 10 ms 2552 KB Output is correct
40 Correct 9 ms 2424 KB Output is correct
41 Correct 9 ms 2296 KB Output is correct
42 Correct 9 ms 2424 KB Output is correct
43 Correct 8 ms 2296 KB Output is correct
44 Correct 9 ms 2424 KB Output is correct
45 Correct 9 ms 2424 KB Output is correct
46 Correct 9 ms 2552 KB Output is correct
47 Correct 9 ms 2424 KB Output is correct
48 Correct 9 ms 2296 KB Output is correct
49 Correct 9 ms 2552 KB Output is correct
50 Correct 9 ms 2428 KB Output is correct
51 Correct 9 ms 2424 KB Output is correct
52 Correct 8 ms 2424 KB Output is correct
53 Correct 9 ms 2428 KB Output is correct
54 Correct 8 ms 2424 KB Output is correct
55 Correct 8 ms 2424 KB Output is correct
56 Correct 9 ms 2424 KB Output is correct
57 Correct 8 ms 2424 KB Output is correct
58 Correct 8 ms 2424 KB Output is correct
59 Correct 5 ms 504 KB Output is correct
60 Correct 6 ms 632 KB Output is correct
61 Correct 5 ms 504 KB Output is correct
62 Correct 5 ms 504 KB Output is correct
63 Correct 6 ms 632 KB Output is correct
64 Correct 6 ms 504 KB Output is correct
65 Correct 9 ms 2424 KB Output is correct
66 Correct 9 ms 2424 KB Output is correct
67 Correct 9 ms 2424 KB Output is correct
68 Correct 9 ms 2552 KB Output is correct
69 Correct 9 ms 2424 KB Output is correct
70 Correct 8 ms 2424 KB Output is correct
71 Correct 7 ms 1016 KB Output is correct
72 Correct 6 ms 1144 KB Output is correct
73 Correct 9 ms 2424 KB Output is correct
74 Correct 8 ms 2552 KB Output is correct
75 Runtime error 515 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
76 Halted 0 ms 0 KB -