Submission #126269

#	Time	Username	Problem	Language	Result	Execution time	Memory
126269		choikiwon	Sparklers (JOI17_sparklers)	C++17	0 / 100	2 ms	376 KiB

sparklers

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

void print(vector<ll> &a) {
    for(int i = 0; i < a.size(); i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
}

int N, K, T;
int X[MN];

bool check(int x) {

    //cout << "check : " << x << endl;

    vector<ll> le, ri;
    for(int i = 0; i < K; i++) {
        ll d = 1LL * T * x - (X[i + 1] - X[i]);
        le.push_back(d);
    }
    reverse(le.begin(), le.end());

    for(int i = K; i < N - 1; i++) {
        ll d = 1LL * T * x - (X[i + 1] - X[i]);
        ri.push_back(d);
    }

    //print(le);
    //print(ri);

    vector<ll> tmp;

    ll sum = 0;
    for(int i = 0; i < le.size(); i++) {
        sum += le[i];
        if(i == (int)le.size() - 1 || ((le[i] >= 0) ^ (le[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
    }

    le = tmp;
    tmp.clear();

    sum = 0;
    for(int i = 0; i < ri.size(); i++) {
        sum += ri[i];
        if(i == (int)ri.size() - 1 || ((ri[i] >= 0) ^ (ri[i + 1] >= 0))) tmp.push_back(sum), sum = 0;
    }

    ri = tmp;

    //print(le);
    //print(ri);

    vector<pair<ll, ll> > L, R;

    ll init = 0;
    ll lim = 0;
    ll neg = 0;
    for(int i = (int)le.size() - 1; i >= 0; i--) {
        if(le[i] >= 0) {
            lim -= le[i];
            neg -= le[i];
        }
        else {
            lim = max(lim - le[i], -le[i]);
            neg -= le[i];
        }
        if(neg > 0) {
            L.push_back({ lim, neg });
            lim = 0;
            neg = 0;
        }
    }
    init -= neg;

    lim = 0;
    neg = 0;
    for(int i = (int)ri.size() - 1; i >= 0; i--) {
        if(ri[i] >= 0) {
            neg -= ri[i];
        }
        else {
            lim = max(lim - ri[i], -ri[i]);
            neg -= ri[i];
        }
        if(neg > 0) {
            R.push_back({ lim, neg });
            lim = 0;
            neg = 0;
        }
    }
    init -= neg;

    //cout << init << endl;

    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    /*
    for(int i = 0; i < L.size(); i++) {
        cout << "(" << L[i].first << ", " << L[i].second << ") ";
    }
    cout << endl;
    for(int i = 0; i < R.size(); i++) {
        cout << "(" << R[i].first << ", " << R[i].second << ") ";
    }
    cout << endl;
    //*/

    vector<ll> psum1(L.size());
    vector<ll> psum2(R.size());

    for(int i = 0; i < L.size(); i++) {
        psum1[i] = L[i].second;
        if(i) psum1[i] += psum1[i - 1];
    }
    for(int i = 0; i < R.size(); i++) {
        psum2[i] = R[i].second;
        if(i) psum2[i] += psum2[i - 1];
    }

    if(init < (psum1.size()? psum1.back() : 0) + (psum2.size()? psum2.back() : 0)) return false;

    vector<int> pnt1(L.size());
    vector<int> pnt2(R.size());

    for(int i = 0; i < L.size(); i++) {
        ll rem = i? init - psum1[i - 1] : init;
        if(rem < L[i].first) return false;
        rem -= L[i].first;

        int s = 0, e = (int)psum2.size() - 1, p = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(psum2[m] <= rem) {
                p = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        pnt1[i] = p;
    }

    for(int i = 0; i < R.size(); i++) {
        ll rem = i? init - psum2[i - 1] : init;
        if(rem < R[i].first) return false;
        rem -= R[i].first;

        int s = 0, e = (int)psum1.size() - 1, p = -1;
        while(s <= e) {
            int m = (s + e)>>1;

            if(psum1[m] <= rem) {
                p = m;
                s = m + 1;
            }
            else e = m - 1;
        }
        pnt2[i] = p;
    }

    int pos = (int)R.size() - 1;
    int mn1 = 1e9;
    int mn2 = 1e9;
    for(int i = (int)L.size() - 1; i >= 0; i--) {
        mn1 = min(mn1, pnt1[i]);
        while(pos >= 0 && pos > mn1) {
            mn2 = min(mn2, pnt2[pos]);
            pos--;
        }
        if(mn2 < i) return false;
    }
    return true;
}

int main() {
    scanf("%d %d %d", &N, &K, &T);
    K--;

    for(int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
    }

    int s = 0, e = 1e9, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(check(2 * m)) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    printf("%d", p);
}

Compilation message (stderr)

sparklers.cpp: In function 'void print(std::vector<long long int>&)':
sparklers.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < le.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ri.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp:118:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < L.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:122:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < R.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < L.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < R.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &K, &T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &X[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50