Submission #232731

#	Time	Username	Problem	Language	Result	Execution time	Memory
232731		thebes	Sparklers (JOI17_sparklers)	C++14	0 / 100	5 ms	384 KiB

sparklers

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef vector<int> vi;
#define F first
#define S second
#define pb push_back

const int MN = 1e5+5;
int N, K, T, i, j, lo, hi, mid, arr[MN];
stack<pdd> l, r;

int main(){
    scanf("%d%d%d",&N,&K,&T);
    for(i=1;i<=N;i++)
        scanf("%d",&arr[i]);
    if(arr[N]==0){
        printf("0\n");
        return 0;
    }
    lo = 1, hi = 1e9;
    while(lo<hi){
        mid = (lo+hi)>>1;
        while(l.size()) l.pop();
        while(r.size()) r.pop();
        for(i=1;i<K;i++){
            pdd cur((arr[i+1]-arr[i])/(double)(2*mid),T-(arr[i+1]-arr[i])/(double)(2*mid));
            while(l.size()&&l.top().F-cur.S<=cur.F&&l.top().S>=0){
                cur.S += l.top().S;
                l.pop();
            }
            l.push(cur);
        }
        for(i=N;i>K;i--){
            pdd cur((arr[i]-arr[i-1])/(double)(2*mid),T-(arr[i]-arr[i-1])/(double)(2*mid));
            while(r.size()&&r.top().F-cur.S<=cur.F&&r.top().S>=0){
                cur.S += r.top().S;
                r.pop();
            }
            r.push(cur);
        }
        int fl = 0;
        double t = T;
        while(l.size()||r.size()){
            if(l.size()&&l.top().S>=0&&l.top().F<=t){
                t += l.top().S;
                l.pop();
            }
            else if(r.size()&&r.top().S>=0&&r.top().F<=t){
                t += r.top().S;
                r.pop();
            }
            else if(l.empty()){
                if(r.top().F>t){fl=1; break;}
                t += r.top().S;
                r.pop();
            }
            else if(r.empty()){
                if(l.top().F>t){fl=1; break;}
                t += l.top().S;
                l.pop();
            }
            else{
                if(min(l.top().F,r.top().F)>t){fl=1; break;}
                vector<pair<double,int>> go;
                if(l.top().F<=t) go.pb({l.top().S,0});
                if(r.top().F<=t) go.pb({r.top().S,1});
                sort(go.begin(),go.end(),[](pair<double,int>i,pair<double,int>j){return i.F>j.F;});
                if(go[0].S==0){
                    t += l.top().S;
                    l.pop();
                }
                else{
                    t += r.top().S;
                    r.pop();
                }
            }
            if(t<0){fl=1; break;}
        }
        if(fl) lo=mid+1;
        else hi=mid;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:17: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:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~

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