Submission #232753

#	Time	Username	Problem	Language	Result	Execution time	Memory
232753		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];
pdd a[MN];

struct SegmentTree{
    struct nd{double mn, ans; int sna;}st[6*MN];
    int n, c;
    void build(int i,int s,int e,vector<double> &vec){
        if(s!=e){
            build(2*i,s,(s+e)/2,vec);
            build(2*i+1,(s+e)/2+1,e,vec);
            st[i].mn = min(st[2*i].mn, st[2*i+1].mn);
            st[i].ans = max(st[2*i].ans, st[2*i+1].ans);
            st[i].sna = (st[i].ans==st[2*i].ans)?st[2*i].sna:st[2*i+1].sna;
        }
        else st[i].mn=st[i].ans=vec[s-1], st[i].sna=s;
    }
    void init(int N,vector<double> vec){
        n = 2*N; c = 1;
        for(int i=1;i<vec.size();i++)
            vec[i] += vec[i-1];
        if(N) build(1,1,n,vec);
    }
    pair<double,int> qu(int i,int s,int e,int ss,int se){
        if(ss>se) return make_pair(-1e9,-1);
        if(s>=ss&&e<=se) return make_pair(st[i].ans,st[i].sna);
        else if((s+e)/2<ss) return qu(2*i+1,(s+e)/2+1,e,ss,se);
        else if((s+e)/2>=se) return qu(2*i,s,(s+e)/2,ss,se);
        else{
            pair<double,int> l=qu(2*i,s,(s+e)/2,ss,se), r=qu(2*i+1,(s+e)/2+1,e,ss,se);
            pair<double,int> ret;
            ret.F=max(l.F,r.F);
            ret.S=l.F==ret.F?l.S:r.S;
            return ret;
        }
    }
    int qu2(int i,int s,int e,int ss,int se,double lim){
        if(ss>se) return -1;
        if(s>=ss&&e<=se){
            if(lim+st[i].mn>=0) return e;
            else if(s==e) return -1;
        }
        else if((s+e)/2<ss) return qu2(2*i+1,(s+e)/2+1,e,ss,se,lim);
        else if((s+e)/2>=se) return qu2(2*i,s,(s+e)/2,ss,se,lim);
        if(st[2*i].mn+lim>=0) return qu2(2*i+1,(s+e)/2+1,e,ss,se,lim);
        else return qu2(2*i,s,(s+e)/2,ss,se,lim);
    }
    pair<double,int> qu(double t){
        if(!n) return make_pair(-1e9,-1);
        else return qu(1,1,n,c,qu2(1,1,n,c,n,t));
    }
    void upd(int idx){
        c=idx;
    }
    bool done(){return c>n;}
}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;
        vector<double> LL, RR;
        for(i=K-1;i>=1;i--){
            LL.pb(-(arr[i+1]-arr[i])/(double)(2*mid));
            LL.pb(T);
        }
        L.init(LL.size(),LL);
        for(i=K+1;i<=N;i++){
            RR.pb(-(arr[i]-arr[i-1])/(double)(2*mid));
            RR.pb(T);
        }
        R.init(RR.size(),RR);
        int fl = 0; double t = T;
        while(!L.done()||!R.done()){
            auto lef = L.qu(t);
            auto rit = R.qu(t);
            if(t+lef.F>=0){
                if(t+rit.F>=0){
                    if(lef.F>rit.F){
                        t += lef.F;
                        L.upd(lef.S+1);
                    }
                    else{
                        t += rit.F;
                        R.upd(rit.S+1);
                    }
                }
                else{
                    t += lef.F;
                    L.upd(lef.S+1);
                }
            }
            else{
                if(t+rit.F<0){fl=1; break;}
                else{
                    t += rit.F;
                    R.upd(rit.S+1);
                }
            }
        }
        if(fl) lo=mid+1;
        else hi=mid;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message (stderr)

sparklers.cpp: In member function 'void SegmentTree::init(int, std::vector<double>)':
sparklers.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1;i<vec.size();i++)
                     ~^~~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:70: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:72: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