oj.uz

답안 #772218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772218 2023-07-03T18:19:01 Z danikoynov Potatoes and fertilizers (LMIO19_bulves) C++14
30 / 100
 191 ms 40420 KB 
#include <iostream>
#include <set> 
#include <cassert>
#include <numeric>
#define endl '\n'
#define int long long
typedef long long ll;

const int BUFF_SIZE = 1e6;
int buffPos = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

void readChar()
{
    if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}

void readInt(int &num)
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
        num = 10 * num + buff[buffPos] - '0';
}

struct slope_trick
{
    const ll inf = 1e18;
 
    std::multiset < ll > left_set, right_set;
    ll height;
 
    slope_trick()
    {
        height = 0;
    }
 
    void add_basic(ll v) /// adds |x - v|
    {
        ll left = -inf;
        ll right = inf;
        if (!left_set.empty())
            left = *left_set.rbegin();
        if (!right_set.empty())
            right = *right_set.begin();
 
 
        if (v >= left && v <= right) /// function on base
        {
            left_set.insert(v);
            right_set.insert(v);
        }
        else
        if (v < left)
        {
                left_set.erase(left_set.find(left));
            right_set.insert(left);
 
            left_set.insert(v);
            left_set.insert(v);
            
            height = height + abs(left - v);
        }
        else
        if (v > right)
        {
            ///std::cout << v << " " << right << endl; 
   
                right_set.erase(right_set.begin());
            left_set.insert(right);
 
            right_set.insert(v);
            right_set.insert(v);
 
            height = height + abs(right - v);
        }
    }
 
 
    void print_slope_trick()
    {
        std::cout << "left_slope" << endl;
        for (int cor : left_set)
            std::cout << cor << " ";
            std::cout << endl;
            std::cout << "right_slope" << endl;
        for (int cor : right_set)
            std::cout << cor << " ";
        std::cout << endl;
        std::cout << "height " << height << endl;
    }
 
    ll get_right()
    {
        if (right_set.empty())
            return inf;
        return *right_set.begin();
    }
 
    ll get_left()
    {
        if (left_set.empty())
            return -inf;
        return *left_set.rbegin();
    }
 
    void prefix_minimum()
    {
        while(left_set.size() > 0)
        {       
            ll val = *left_set.begin();
            if (val >= 0)
                break;
                assert(left_set.size() > 0);
            left_set.erase(left_set.find(val));
        }
 
        ll slope = 0, base = height, last = get_right();
        
        while (get_right() <= 0)
        {
            ll distance = get_right() - last;
            base = base + distance * slope;
            slope ++;
            last = last + distance;
            assert(right_set.size() > 0);
            right_set.erase(right_set.begin());
        }
        
        if (slope != 0)
        {
            base = base + (- last) * slope;
            right_set.insert(0);
        }
        height = base;
 
        right_set.clear();
        ///right_set.clear();
    }
 
    ll query_vlaue(ll debit)
    {   
        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && last > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            assert(left_set.size() > 0);
            left_set.erase(left_set.find(*left_set.rbegin()));
        }

        if (slope != 0)
        {
            base = base + (last - debit) * slope;
        }
 
        return base;
    }
};
 
 
const int maxn = 500010;
 
int n;
int a[maxn], b[maxn];
ll x[maxn], pref[maxn];
 
void solve()
{
    readInt(n);
    for (int i = 1; i <= n; i ++)
    {
        readInt(a[i]);
        readInt(b[i]);
        x[i] = a[i] - b[i];
        pref[i] = pref[i - 1] + x[i];
    }
 
    slope_trick st;
    for (int i = 1; i <= n; i ++)
    {
        st.add_basic(pref[i]);
        st.prefix_minimum();
        //std::cout << "--------------------" << endl;
        //st.print_slope_trick();
    }
    ///std::cout << "dasdas" << endl;
    ll ans = st.query_vlaue(pref[n]);
    ///std::cout << "-----------------" << endl;
    std::cout << ans << endl;
}
 
void speed()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}
 
signed main()
{
    speed();
    solve();
    return 0;
}

Compilation message

bulves.cpp: In member function 'void slope_trick::print_slope_trick()':
bulves.cpp:83:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |         for (int cor : left_set)
      |         ^~~
bulves.cpp:85:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |             std::cout << endl;
      |             ^~~
bulves.cpp: In function 'void readChar()':
bulves.cpp:15:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 13 ms 3156 KB Output is correct
5 Correct 28 ms 6228 KB Output is correct
6 Correct 100 ms 20396 KB Output is correct
7 Correct 82 ms 18356 KB Output is correct
8 Incorrect 191 ms 40420 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 13 ms 3156 KB Output is correct
5 Correct 28 ms 6228 KB Output is correct
6 Correct 100 ms 20396 KB Output is correct
7 Correct 82 ms 18356 KB Output is correct
8 Incorrect 191 ms 40420 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 468 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 13 ms 3156 KB Output is correct
12 Correct 28 ms 6228 KB Output is correct
13 Correct 100 ms 20396 KB Output is correct
14 Correct 82 ms 18356 KB Output is correct
15 Incorrect 191 ms 40420 KB Output isn't correct
16 Halted 0 ms 0 KB -