Submission #1095886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095886		guagua0407	Meetings (IOI18_meetings)	C++17	0 / 100	5542 ms	21076 KiB

meetings

#pragma GCC optimize("Ofast")
#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=320;
const int mxn=1e5+5;
const int inf=1e9;
int n;
vector<vector<int>> lst,rst;
vector<int> h;
int L=0,R=0;
vector<int> 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,int 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]);
}

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

void updl(int l,int 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,h[rst[l][pos]]*(r-rst[l][pos])*d);
        update(max(l+1,rst[l][pos]),r-1,h[rst[l][pos]]*d);
        pos--;
    }
}

void updr(int r,int 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);
        update(r,r,h[lst[r][pos]]*(lst[r][pos]-l)*d);
        update(l+1,min(r-1,lst[r][pos]),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<int>(4*n);
    lazy=vector<int>(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]);
    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]=query(L[id],R[id]);
        }
    }
    return ans;
}
/*
4 2
2 4 3 5
0 2
1 3
*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40