Submission #1264482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264482		pythontest	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	690 ms	124220 KiB

Main

#include <deque>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct nodeliniowka {
    long long a,b;
    nodeliniowka operator +(const nodeliniowka& x)  const{
        nodeliniowka res;
        res.a = this->a+x.a;
        res.b = this->b+x.b;
        return res;
    }
    void operator +=(const nodeliniowka& x) {
        this->a+=x.a;
        this->b+=x.b;
    }
    bool operator <(const nodeliniowka& x) const {
        if (this->a==x.a) return this->b<x.b;
        return this->a<x.a;
    }
};
struct zapytanie {
    long long u;
    int a; int b;
    int indeks;
    bool operator <(const zapytanie& x) const {
        return this->u<x.u;
    }
};

typedef pair<long long, long long> treepair;
typedef pair<long long, pair<long long, int>> treepairext;
struct przejscie {
    long long warunek;
    int indeks;
    int priorytet;
    nodeliniowka v;
    bool operator < (const przejscie& x) const {
        if (this->warunek==x.warunek) return this->priorytet<x.priorytet;
        return this->warunek<x.warunek;
    }
};
constexpr int MJ=20;
constexpr int N = 1<<(MJ-2);
constexpr long long INF=1e14;
int n,q;
nodeliniowka drzewoliniowek[1<<MJ];
treepairext drzewominmaksow[1<<MJ];
vector<long long> prefdist, dist, cost;
long long dl[N],dr[N], jp[N][MJ], sjp[N][MJ];
void updatelin(int n, nodeliniowka v) {
    n+=1<<(MJ-1);
    drzewoliniowek[n] = v;
    n>>=1;
    while (n>0) {
        drzewoliniowek[n] = drzewoliniowek[2*n]+drzewoliniowek[2*n+1];
        n>>=1;
    }
}
nodeliniowka readlin(int a, int b) {
    a+=1<<(MJ-1);b+=1<<(MJ-1);
    if (a>b) return {0,0};
    nodeliniowka res=drzewoliniowek[a];
    if (a==b) return res;
    res+=drzewoliniowek[b];
    while ((a>>1)!=(b>>1)) {
        if (a%2==0) res+= drzewoliniowek[a+1];
        if (b%2==1) res+=drzewoliniowek[b-1];
        a>>=1;
        b>>=1;
    }
    return res;
}
void updateminmaks(int n, treepair v) {
    n+=1<<(MJ-1);
    drzewominmaksow[n]={v.first,{v.second,-(n-(1<<(MJ-1)))}};
    n>>=1;
    while (n>0) {
        drzewominmaksow[n].first=max(drzewominmaksow[2*n].first,drzewominmaksow[2*n+1].first);
        drzewominmaksow[n].second=min(drzewominmaksow[2*n].second,drzewominmaksow[2*n+1].second);
        n>>=1;
    }
}
treepairext readminmaks(int a, int b) {
    a+=1<<(MJ-1);b+=1<<(MJ-1);
    treepairext res = drzewominmaksow[a];
    res.first = max(res.first,drzewominmaksow[b].first);
    res.second = min(res.second,drzewominmaksow[b].second);
    while ((a>>1)!=(b>>1)) {
        if (a%2==0) {
            res.first = max(res.first,drzewominmaksow[a+1].first);
            res.second = min(res.second,drzewominmaksow[a+1].second);
        }
        if (b%2==1) {
            res.first = max(res.first,drzewominmaksow[b-1].first);
            res.second = min(res.second,drzewominmaksow[b-1].second);
        }
        a>>=1;
        b>>=1;
    }
    res.second.second = -res.second.second;
    return res;
}
void compdarray(long long *array, int begin, bool compjp=false, int inc=1) {
    deque<pair<int,long long>> kolejkamon;
    for (int i=0;i<N;i++) updateminmaks(i,{0,INF});
    for (int i=begin;i>0&&i<=n;i+=inc) {
        auto besto = readminmaks(0,cost[i]-(compjp?0:1));
        long long best = besto.first;
        if (inc<0) best = besto.second.first;
        jp[i][0]=n+1;
        sjp[i][0]=(prefdist[n+1]-prefdist[i])*cost[i];
        if (best==0 || best==INF) array[i]=INF;
        else {
            array[i]=abs(prefdist[i]-prefdist[best]);
            jp[i][0]=best;
            sjp[i][0]=abs(prefdist[i]-prefdist[best])*cost[i];
        }
        updateminmaks(cost[i],{i,i});
    }
    for (int i=0;i<N;i++) updateminmaks(i,{0,INF});
}
int main() {
    scanf("%d %d",&n,&q);
    dist.resize(n+2);cost.resize(n+2); prefdist.resize(n+2);
    for (int i=1;i<=n;i++) scanf("%lld",&dist[i]);
    for (int i=1;i<=n;i++) scanf("%lld",&cost[i]);
    cost[0]=1e18;
    for (int i=2;i<=n+1;i++) prefdist[i]=prefdist[i-1]+dist[i-1];

    vector<zapytanie> zapytania(q);
    for (int i=0;i<q;i++) scanf("%d %d %lld",&zapytania[i].a,&zapytania[i].b,&zapytania[i].u);
    for (int i=0;i<q;i++) zapytania[i].indeks=i;
    sort(zapytania.begin(),zapytania.end());
    compdarray(dl, 1);
    compdarray(dr,n,true,-1);
    for (int i=1;i<=n;i++) updateminmaks(i,{dist[i],cost[i]});
    jp[n+1][0]=n+1;
    // updateminmaks(n+1,{0,0});
    for (int i=n+1;i>0;i--) {
        for (int j=1;j<MJ;j++) {
            jp[i][j]=jp[jp[i][j-1]][j-1];
            sjp[i][j]=sjp[i][j-1]+sjp[jp[i][j-1]][j-1];
        }
    }
    vector<przejscie> przejscia;
    for (int i=1;i<=n;i++) {
        przejscia.push_back({0,i,0,{cost[i],0}});
        przejscia.push_back({min(dl[i],dr[i]),i,1,{0,min(dl[i],dr[i])*cost[i]}});
        przejscia.push_back({dl[i]+dr[i]-min(dl[i],dr[i]),i,2,{-cost[i],(dl[i]+dr[i])*cost[i]}});
        przejscia.push_back({dl[i]+dr[i],i,3,{0,0}});
    }
    sort(przejscia.begin(),przejscia.end());
    int przejsciapointer=0;
    vector<long long> odpowiedz(q);
    for (auto x:zapytania) {
        while (przejsciapointer<przejscia.size() && przejscia[przejsciapointer].warunek<=x.u) {
            updatelin(przejscia[przejsciapointer].indeks,przejscia[przejsciapointer].v);
            przejsciapointer++;
        }
        if (readminmaks(x.a,x.b-1).first > x.u) {
            odpowiedz[x.indeks]=-1;
            continue;
        }
        long long maksbeg = prefdist[x.a]+x.u, maksend = prefdist[x.b]-x.u;
        auto itb = upper_bound(prefdist.begin(),prefdist.end(),maksbeg), ite = lower_bound(prefdist.begin(),prefdist.end(),maksend);
        itb--;
        int granicaleft = min((int)(itb-prefdist.begin()),x.b), granicaright = max(x.a, (int)(ite-prefdist.begin()));
        int l = x.a;
        long long wyn=0;
        for (int i=MJ-1;i>=0;i--)
            if (jp[l][i]<=granicaleft) {
                wyn+=sjp[l][i];
                l=jp[l][i];
            }
        if (l!=x.b) {
            wyn+=min(x.u,min(dr[l],prefdist[x.b]-prefdist[l]))*cost[l];
            l++;
        }
        auto mini = readminmaks(max(granicaright,l),x.b).second;
        auto liniowe = readlin(l,mini.second-1);

        // wyn+=(prefdist[min(l+1,x.b)]-prefdist[l])*cost[l];
        wyn+=liniowe.a*x.u + liniowe.b;
        if (l!=x.b) {
            wyn+=(prefdist[x.b]-prefdist[mini.second])*mini.first;
            if (mini.second != x.b) {
                if (dl[mini.second] <= prefdist[mini.second]-prefdist[x.a] && true)
                    wyn -= min(prefdist[x.b]-prefdist[mini.second],max(0ll,x.u-dl[mini.second]))*mini.first;
            }
        }
        odpowiedz[x.indeks]=wyn;
    }
    for (int i=0;i<q;i++) printf("%lld\n",odpowiedz[i]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:127:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     for (int i=1;i<=n;i++) scanf("%lld",&dist[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:128:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     for (int i=1;i<=n;i++) scanf("%lld",&cost[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:133:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     for (int i=0;i<q;i++) scanf("%d %d %lld",&zapytania[i].a,&zapytania[i].b,&zapytania[i].u);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44