Submission #1016178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016178		Unforgettablepl	Meetings (IOI18_meetings)	C++17	19 / 100	5557 ms	249380 KiB

meetings

#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"

const int SQRT = 50;

struct Query{
    int L,R,idx;
    Query(int L,int R,int idx):L(L),R(R),idx(idx){}
    bool operator<(const Query& other)const{
        return L/SQRT == other.L/SQRT ? R<other.R : L<other.L;
    }
};

struct Segtree{ // Range add, range min
    vector<long long> tree,lazy;
    int N;
    Segtree(int N):tree(4*N),lazy(4*N),N(N){}
    void update(int qL,int qR,int qX,int x,int L,int R){
        if(lazy[x]){
            tree[x]+=lazy[x];
            if(L!=R){
                lazy[2*x]+=lazy[x];
                lazy[2*x+1]+=lazy[x];
            }
            lazy[x]=0;
        }
        if(qR<L or R<qL)return;
        if(qL<=L and R<=qR){
            tree[x]+=qX;
            if(L!=R){
                lazy[2*x]+=qX;
                lazy[2*x+1]+=qX;
            }
            return;
        }
        int mid = (L+R)/2;
        update(qL,qR,qX,2*x,L,mid);
        update(qL,qR,qX,2*x+1,mid+1,R);
        tree[x] = min(tree[2*x],tree[2*x+1]);
    }
    void update(int qL,int qR,int qX){
        update(qL,qR,qX,1,0,N-1);
    }
    long long get(int qL,int qR,int x,int L,int R){
        if(lazy[x]){
            tree[x]+=lazy[x];
            if(L!=R){
                lazy[2*x]+=lazy[x];
                lazy[2*x+1]+=lazy[x];
            }
            lazy[x]=0;
        }
        if(qR<L or R<qL)return INT64_MAX;
        if(qL<=L and R<=qR)return tree[x];
        int mid = (L+R)/2;
        return min(get(qL,qR,2*x,L,mid),get(qL,qR,2*x+1,mid+1,R));
    }
    long long get(int qL,int qR){return get(qL,qR,1,0,N-1);}
};

vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                vector<int> R) {
    int n = H.size();
    int q = L.size();
    Segtree cost(n);
    vector<stack<pair<int,int>>> fromleft(n);
    vector<stack<pair<int,int>>> fromright(n);
    {
        // from left calculation
        stack<pair<int,int>> s;
        s.emplace(INT32_MAX,-1);
        for(int i=0;i<n;i++){
            while(s.top().first<=H[i])s.pop();
            s.emplace(H[i],i);
            fromleft[i] = s;
        }
    }
    {
        // from right calculation
        stack<pair<int,int>> s;
        s.emplace(INT32_MAX,n);
        for(int i=n-1;i>=0;i--){
            while(s.top().first<=H[i])s.pop();
            s.emplace(H[i],i);
            fromright[i] = s;
        }
    }
    auto add = [&](int x,int offset){
        {
            // from left calculation
            stack<pair<int,int>> s = fromleft[x];
            while(s.size()>1){
                auto [curr,idx] = s.top();s.pop();
                cost.update(s.top().second+1,idx,curr*offset);
            }
        }
        {
            // from right calculation
            stack<pair<int,int>> s = fromright[x];
            s.top().second++;
            while(s.size()>1){
                auto [curr,idx] = s.top();s.pop();
                cost.update(idx,s.top().second-1,curr*offset);
            }
        }
    };
    int l = 0;
    int r = -1;
    vector<long long> ans(q);
    vector<Query> queries;
    for(int i=0;i<q;i++)queries.emplace_back(L[i],R[i],i);
    sort(queries.begin(),queries.end());
    for(auto[tarL,tarR,idx]:queries){
        while(l<tarL)add(l++,-1);
        while(tarL<l)add(--l,1);
        while(r<tarR)add(++r,1);
        while(tarR<r)add(r--,-1);
        ans[idx] = cost.get(tarL,tarR);
    }
    return ans;
}

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