oj.uz

Submission #100301

# Submission time Handle Problem Language Result Execution time Memory
100301 2019-03-10T10:23:49 Z chpipis Simfonija (COCI19_simfonija) C++11
110 / 110
 141 ms 11000 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAX_N = 1e5 + 5;

int a[MAX_N], b[MAX_N];
int pos[MAX_N];

struct slope_ds {
    multiset<int> one, two;
    ll val;

    slope_ds() {
        val = 0;
    }

    void add(int p) {
        if (one.empty()) {
            one.insert(p);
            two.insert(p);
            val = 0;
            return;
        }
        int opt = *one.rbegin();
        val += abs(opt - p);
        if (opt < p) {
            two.insert(p);
            two.insert(p);
            one.insert(*two.begin());
            two.erase(two.begin());
        } else {
            one.insert(p);
            one.insert(p);
            two.insert(*one.rbegin());
            one.erase(prev(one.end()));
        }
        val -= abs(opt - *one.rbegin());
    }

    void rem(int p) {
        int opt = *one.rbegin();
        val -= abs(opt - p);
        if (opt < p) {
            two.insert(*one.rbegin());
            one.erase(prev(one.end()));
            two.erase(two.find(p));
            two.erase(two.find(p));
        } else {
            one.insert(*two.begin());
            two.erase(two.begin());
            one.erase(one.find(p));
            one.erase(one.find(p));
        }
        val -= abs(opt - *one.rbegin());
    }
};

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; i++) {
        pos[i] = a[i] - b[i];
    }
    sort(pos + 1, pos + n + 1);
    slope_ds myds;
    for (int i = 1; i <= n - k; i++) {
        myds.add(pos[i]);
    }
    ll ans = myds.val;
    for (int i = 1; i <= k; i++) {
        myds.add(pos[n - k + i]);
        myds.rem(pos[i]);
        ans = min(ans, myds.val);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

simfonija.cpp: In function 'int main()':
simfonija.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
simfonija.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
simfonija.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 10932 KB Output is correct
2 Correct 94 ms 11000 KB Output is correct
3 Correct 113 ms 10844 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10872 KB Output is correct
2 Correct 115 ms 10948 KB Output is correct
3 Correct 126 ms 10968 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 10860 KB Output is correct
2 Correct 141 ms 10872 KB Output is correct
3 Correct 104 ms 10892 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 4336 KB Output is correct
2 Correct 114 ms 5008 KB Output is correct
3 Correct 115 ms 4472 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 8444 KB Output is correct
2 Correct 100 ms 3100 KB Output is correct
3 Correct 107 ms 5668 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1804 KB Output is correct
2 Correct 134 ms 7696 KB Output is correct
3 Correct 115 ms 4660 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 5368 KB Output is correct
2 Correct 107 ms 5212 KB Output is correct
3 Correct 110 ms 7364 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 6816 KB Output is correct
2 Correct 70 ms 1660 KB Output is correct
3 Correct 133 ms 10868 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 8056 KB Output is correct
2 Correct 118 ms 10896 KB Output is correct
3 Correct 116 ms 8676 KB Output is correct