oj.uz

Submission #1095756

# Submission time Handle Problem Language Result Execution time Memory
1095756 2024-10-03T06:41:42 Z guagua0407 Meetings (IOI18_meetings) C++17
19 / 100
 2299 ms 40824 KB 
#pragma GCC optimize("O3")
#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int B=300;
const int mxn=1e5+5;
const ll inf=1e18;
int n;
vector<vector<int>> lst,rst;
vector<int> h;
int L=0,R=0;
vector<ll> segtree,lazy;

void push(int v){
    if(lazy[v]==0) return;
    segtree[v*2]+=lazy[v];
    segtree[v*2+1]+=lazy[v];
    lazy[v*2]+=lazy[v];
    lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}

void update(int tl,int tr,ll val,int l=0,int r=n-1,int v=1){
    if(r<tl or tr<l){
        return;
    }
    if(tl<=l and r<=tr){
        segtree[v]+=val;
        lazy[v]+=val;
        return;
    }
    int mid=(l+r)/2;
    push(v);
    update(tl,min(mid,tr),val,l,mid,v*2);
    update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
    segtree[v]=min(segtree[v*2],segtree[v*2+1]);
}

void updl(int l,int d){
    update(l,l,1ll*(-inf)*d);
    int pos=(int)rst[l].size()-1;
    while(pos>=0 and rst[l][pos]<=R){
        int r=(pos>=1?rst[l][pos-1]:mxn);
        r=min(r,R+1);
        update(l,l,1ll*h[rst[l][pos]]*(r-rst[l][pos])*d);
        update(max(l+1,rst[l][pos]),r-1,1ll*h[rst[l][pos]]*d);
        pos--;
    }
}

void updr(int r,int d){
    //cout<<"r "<<r<<' '<<d<<'\n';
    update(r,r,1ll*(-inf)*d);
    int pos=(int)lst[r].size()-1;
    while(pos>=0 and lst[r][pos]>=L){
        int l=(pos>=1?lst[r][pos-1]:-1);
        l=max(l,L-1);
        //cout<<r<<' '<<r<<' '<<1ll*h[lst[r][pos]]*(lst[r][pos]-l)*d<<'\n';
        update(r,r,1ll*h[lst[r][pos]]*(lst[r][pos]-l)*d);
        //cout<<l+1<<' '<<lst[r][pos]<<' '<<1ll*h[lst[r][pos]]*d<<'\n';
        update(l+1,min(r-1,lst[r][pos]),1ll*h[lst[r][pos]]*d);
        pos--;
    }
}

void sir(int l,int r){
    while(L>l){
        L--;
        updl(L,1);
    }
    while(R<r){
        R++;
        updr(R,1);
    }
    while(L<l){
        updl(L,-1);
        L++;
    }
    while(R>r){
        updr(R,-1);
        R--;
    }
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
    h=H;
    n=(int)H.size();
    lst.resize(n);
    rst.resize(n);
    segtree=vector<ll>(4*n);
    lazy=vector<ll>(4*n);
    {
        vector<int> st;
        for(int i=0;i<n;i++){
            while(!st.empty() and h[i]>=h[st.back()]){
                st.pop_back();
            }
            st.push_back(i);
            lst[i]=st;
        }
    }
    {
        vector<int> st;
        for(int i=n-1;i>=0;i--){
            while(!st.empty() and h[i]>=h[st.back()]){
                st.pop_back();
            }
            st.push_back(i);
            rst[i]=st;
        }
    }
    int q=(int)L.size();
    vector<vector<pair<int,int>>> qs(B);
    for(int i=0;i<q;i++){
        qs[L[i]/B].push_back({R[i],i});
    }
    update(0,0,h[0]);
    update(1,n-1,inf);
    vector<ll> ans(q);
    bool tf=false;
    for(int i=0;i<B;i++){
        if(qs[i].empty()) continue;
        if(!tf) sort(all(qs[i]));
        else sort(qs[i].rbegin(),qs[i].rend());
        tf=!tf;
        for(auto v:qs[i]){
            int id=v.s;
            sir(L[id],R[id]);
            ans[id]=segtree[1];
        }
    }
    return ans;
}
/*
4 2
2 4 3 5
0 2
1 3
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 856 KB Output is correct
3 Correct 9 ms 860 KB Output is correct
4 Correct 17 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 964 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 856 KB Output is correct
3 Correct 9 ms 860 KB Output is correct
4 Correct 17 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 964 KB Output is correct
10 Correct 986 ms 1796 KB Output is correct
11 Correct 251 ms 1808 KB Output is correct
12 Correct 782 ms 1760 KB Output is correct
13 Correct 257 ms 1740 KB Output is correct
14 Correct 235 ms 1624 KB Output is correct
15 Correct 763 ms 1624 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2299 ms 3484 KB Output is correct
3 Runtime error 47 ms 40824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2299 ms 3484 KB Output is correct
3 Runtime error 47 ms 40824 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 856 KB Output is correct
3 Correct 9 ms 860 KB Output is correct
4 Correct 17 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 964 KB Output is correct
10 Correct 986 ms 1796 KB Output is correct
11 Correct 251 ms 1808 KB Output is correct
12 Correct 782 ms 1760 KB Output is correct
13 Correct 257 ms 1740 KB Output is correct
14 Correct 235 ms 1624 KB Output is correct
15 Correct 763 ms 1624 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2299 ms 3484 KB Output is correct
18 Runtime error 47 ms 40824 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -