oj.uz

답안 #91591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91591 2018-12-28T14:41:09 Z Alexa2001 Sparklers (JOI17_sparklers) C++17
0 / 100
 2 ms 456 KB 
#include <bits/stdc++.h>

using namespace std;

const int lim = 1e9, Nmax = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> Pair;
const ll Target = 1e16;

int n, K, T;
int X[Nmax];

void add(vector<Pair> &w, ll A, ll B)
{
    while(w.size())
    {
        if(B >= w.back().first)
            B += w.back().second - w.back().first;
        else if(A > B)
        {
            A += w.back().first - B;
            B = w.back().second;
        }
        else break;
        w.pop_back();
    }

  //  assert(A <= B);
  //  if(w.size()) assert(w.back().first >= B);
    w.push_back({A, B});
}

ll transformm(vector<int> &v, vector<Pair> &w)
{
    int i = 0;
    ll sum = 0, K, Q;

    while(i<v.size() && v[i] > 0) sum += v[i++];

    add(w, 0, Target);
    vector<Pair> to_add;

    for(; i<v.size(); )
    {
        K = 0;
        while(i < v.size() && v[i] <= 0) K += v[i++];
        Q = 0;
        while(i < v.size() && v[i] > 0) Q += v[i++];
        to_add.push_back({-K, Q});
    }

    reverse(to_add.begin(), to_add.end());
    for(auto it : to_add)
        add(w, it.first, it.second);
    reverse(w.begin(), w.end());
    return sum;
}

void Merge(vector<Pair> &a, vector<Pair> &b, vector<Pair> &c)
{
    int i = 0, j = 0;
    while(c.size() < a.size() + b.size())
    {
        if(i < a.size() && (j == b.size() || a[i] < b[j]))
            c.push_back(a[i++]);
        else c.push_back(b[j++]);
    }
}

bool check(int S)
{
    if(2LL * S * T >= lim) return 1;

    vector<int> A, B;

    int i;
    for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
    for(i=K+1; i<=n; ++i) B.push_back(2 * S * T - (X[i] - X[i-1]));

    vector<Pair> a, b, c;
    ll sum = 0;
    sum = transformm(A, a) + transformm(B, b);
    Merge(a, b, c);

    for(auto it : c)
    {
        if(sum < it.first) break;
        sum -= it.first;
        sum += it.second;
    }
    return (sum >= 2 * Target);
}

int main()
{
/// freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n >> K >> T;
    for(i=1; i<=n; ++i) cin >> X[i];

    int st = 0, dr = 1e9, mid;
    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }

    cout << st << '\n';
    return 0;
}

Compilation message

sparklers.cpp: In function 'll transformm(std::vector<int>&, std::vector<std::pair<long long int, long long int> >&)':
sparklers.cpp:38:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<v.size() && v[i] > 0) sum += v[i++];
           ~^~~~~~~~~
sparklers.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; i<v.size(); )
           ~^~~~~~~~~
sparklers.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < v.size() && v[i] <= 0) K += v[i++];
               ~~^~~~~~~~~~
sparklers.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i < v.size() && v[i] > 0) Q += v[i++];
               ~~^~~~~~~~~~
sparklers.cpp: In function 'void Merge(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&)':
sparklers.cpp:64:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < a.size() && (j == b.size() || a[i] < b[j]))
            ~~^~~~~~~~~~
sparklers.cpp:64:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < a.size() && (j == b.size() || a[i] < b[j]))
                             ~~^~~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
     ^~~
sparklers.cpp:77:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=1; i<K; ++i) A.push_back(2 * S * T - (X[i+1] - X[i])); reverse(A.begin(), A.end());
                                                                  ^~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Incorrect 2 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Incorrect 2 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Incorrect 2 ms 456 KB Output isn't correct
4 Halted 0 ms 0 KB -