oj.uz

Submission #1043280

# Submission time Handle Problem Language Result Execution time Memory
1043280 2024-08-04T07:40:24 Z amirhoseinfar1385 Distributing Candies (IOI21_candies) C++17
0 / 100
 100 ms 28352 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,sq=450,msq=maxn/sq+10,lg=19;
long long n,m,all[maxn],tr[maxn];
struct qu{
    long long l,r,w;
}allq[maxn];
/*struct segment{

};
struct bl{
    vector<pair<long long,long long>>allv;
    void upd(long long w,long long ind){
        allv.push_back(make_pair(w,ind));
    }
}allsq[msq];*/

struct fenwick{
    long long fn[maxn];
    void add(long long i,long long w){
        i++;
        while(i<maxn){
            fn[i]+=w;
            i+=((-i)&i);
        }
    }
    long long pors(long long i){
        long long ret=0;
        i++;
        while(i>0){
            ret+=fn[i];
            i-=((-i)&i);
        }
        return ret;
    }
}fen;

vector<int> khor(){
    vector<int>ret(n);
    vector<pair<long long,long long>>tof;
    for(long long i=1;i<=n;i++){
        tof.push_back(make_pair(2*tr[i]+1,i));
    }
    for(long long i=1;i<=m;i++){
        tof.push_back(make_pair(2*i,i));
    }
    sort(tof.begin(),tof.end());
    while((long long)tof.size()>0){
        auto x=tof.back();
        tof.pop_back();
        if(x.first&1){
            ret[x.second-1]=fen.pors(x.second);
        }else{
            fen.add(allq[x.second].l,allq[x.second].w);
            fen.add(allq[x.second].r+1,allq[x.second].w*-1);
        }
    }
    for(int i=0;i<n;i++){
        if(tr[i+1]!=0&&allq[tr[i+1]].w>0){
            ret[i]=all[i+1]+ret[i];
        }
    }
    return ret;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=(long long)c.size();
    m=(long long)l.size();
    for(long long i=1;i<=n;i++){
        all[i]=c[i-1];
    }
    for(int i=1;i<=m;i++){
        l[i-1]++;
        r[i-1]++;
        allq[i].l=l[i-1];
        allq[i].r=r[i-1];
        allq[i].w=v[i-1];
    }
    deque<pair<long long ,long long>>manf,mos;
    long long now=0,mx=0,mn=0;
    for(long long i=1;i<=m;i++){
        now+=allq[i].w;
        mn=min(mn,now);
        mx=max(mx,now);
        if(allq[i].w>0){
            long long wa=now-mn;
            while((long long)mos.size()>0&&mos.front().first<=wa){
                mos.pop_front();
            }
            mos.push_front(make_pair(wa,i));
        }else{
            long long wa=mx-now;
            wa*=-1;
            while((long long)manf.size()>0&&manf.back().first>=wa){
                manf.pop_back();
            }
            manf.push_back(make_pair(wa,i));
        }
    }
    for(long long i=1;i<=n;i++){
        long long p=lower_bound(mos.begin(),mos.end(),make_pair(all[i],-1ll))-mos.begin();
        if(p!=(long long)mos.size()){
            tr[i]=mos[p].second;
        }
        p=upper_bound(manf.begin(),manf.end(),make_pair(-all[i]+1,-1ll))-manf.begin();
        p--;
        if(p>=0){
            tr[i]=max(tr[i],manf[p].second);
        }
      //  cout<<i<<" "<<tr[i]<<endl;
    }
    return khor();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 28352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -