Submission #126351

#	Time	Username	Problem	Language	Result	Execution time	Memory
126351		choikiwon	Sparklers (JOI17_sparklers)	C++17	100 / 100	88 ms	3988 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;
    if(le.size() && le[0] >= 0) init += le[0], le.erase(le.begin());
    if(ri.size() && ri[0] >= 0) init += ri[0], ri.erase(ri.begin());
    if(le.size() % 2) le.push_back(0);
    if(ri.size() % 2) ri.push_back(0);

    for(int i = 0; i < le.size(); i += 2) {
        ll n = -le[i];
        ll p = le[i + 1];

        L.push_back({ n, n - p });

        while(L.size() >= 2 && L.back().second <= 0 && L[ (int)L.size() - 2 ].second > 0) {
            pair<ll, ll> d = L.back(); L.pop_back();
            pair<ll, ll> t = L.back(); L.pop_back();

            t.first = max(t.first, t.second + d.first);
            t.second += d.second;
            L.push_back(t);
        }
    }
    for(int i = 0; i < ri.size(); i += 2) {
        ll n = -ri[i];
        ll p = ri[i + 1];

        R.push_back({ n, n - p });

        while(R.size() >= 2 && R.back().second <= 0 && R[ (int)R.size() - 2 ].second > 0) {
            pair<ll, ll> d = R.back(); R.pop_back();
            pair<ll, ll> t = R.back(); R.pop_back();

            t.first = max(t.first, t.second + d.first);
            t.second += d.second;
            R.push_back(t);
        }
    }

    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;
    //*/

    while(1) {
        if(L.size() && L.back().second <= 0 && init >= L.back().first) {
            init -= L.back().second, L.pop_back();
            continue;
        }
        if(R.size() && R.back().second <= 0 && init >= R.back().first) {
            init -= R.back().second, R.pop_back();
            continue;
        }
        break;
    }
    if(L.size() && L.back().second <= 0) return false;
    if(R.size() && R.back().second <= 0) return false;

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

    //cout << init << endl;

    /*
    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--;

    //N = 1000, K = 510, T = 1;

    for(int i = 0; i < N; i++) {
        scanf("%d", &X[i]);
        /*
        X[i] = rand() + rand();
        if(i) X[i] += X[i - 1];
        //*/
    }

    int s = 0, e = 1e9 / T + 1, 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:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < le.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ri.size(); i++) {
                    ~~^~~~~~~~~~~
sparklers.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < le.size(); i += 2) {
                    ~~^~~~~~~~~~~
sparklers.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ri.size(); i += 2) {
                    ~~^~~~~~~~~~~
sparklers.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < L.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:153:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < R.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < L.size(); i++) {
                    ~~^~~~~~~~~~
sparklers.cpp:181: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:214: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:220:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &X[i]);
         ~~~~~^~~~~~~~~~~~~

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