Submission #1123731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123731		Pacybwoah	Meetings (IOI18_meetings)	C++20	41 / 100	2128 ms	14848 KiB

meetings

#include "meetings.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    int n, q;
    vector<ll> vec;
}
struct node{
    ll maxi, tag;
    node(ll a, ll b){
        maxi = a, tag = b;
    }
};
struct st{
    vector<node> seg;
    st(int N){
        seg.resize(4 * N + 4, node(0, 0));
    }
    void push(int l, int r, int ind){
        if(l == r) return;
        seg[ind * 2].maxi += seg[ind].tag;
        seg[ind * 2 + 1].maxi += seg[ind].tag;
        seg[ind * 2].tag += seg[ind].tag;
        seg[ind * 2 + 1].tag += seg[ind].tag;
        seg[ind].tag = 0;
    }
    void modify(int l, int r, int start, int end, ll val, int ind){
        if(r < start || end < l) return;
        if(start <= l && r <= end){
            seg[ind].maxi += val;
            seg[ind].tag += val;
            return;
        }
        int mid = (l + r) >> 1;
        push(l, r, ind);
        modify(l, mid, start, end, val, ind * 2);
        modify(mid + 1, r, start, end, val, ind * 2 + 1);
        seg[ind].maxi = max(seg[ind * 2].maxi, seg[ind * 2 + 1].maxi);
    }
    ll query(int l, int r, int start, int end, int ind){
        if(r < start || end < l) return 0;
        if(start <= l && r <= end) return seg[ind].maxi;
        push(l, r, ind);
        int mid = (l + r) >> 1;
        return max(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
    }
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    n = H.size();
    q = L.size();
    vec.resize(n + 1);
    for(int i = 1; i <= n; i++) vec[i] = H[i - 1], assert(vec[i] <= 20);
    vector<ll> ans(q);
    st seg(n);
    vector<vector<pair<int, int>>> rngs(21);
    for(int i = 1; i < 20; i++){
        int curl = -1;
        bool flag = 0;
        for(int j = 1; j <= n; j++){
            if(vec[j] <= i){
                if(curl == -1) curl = j;
                flag = 1;
            }
            else{
                if(flag){
                    rngs[i].emplace_back(curl, j - 1);
                }
                flag = 0;
                curl = -1;
            }
        } 
        if(curl > 0) rngs[i].emplace_back(curl, n);
    }
    for(int i = 1; i < 20; i++){
        for(auto &[l, r]: rngs[i]){
            seg.modify(1, n, l, r, r - l + 1, 1);
        }
    }
    for(int hey = 0; hey < q; hey++){
        int l = L[hey] + 1, r = R[hey] + 1;
        for(int i = 1; i < 20; i++){
            auto iter = lower_bound(rngs[i].begin(), rngs[i].end(), make_pair(l, 0));
            if(iter != rngs[i].begin()){
                auto &[curl, curr] = (*prev(iter));
                if(l <= curr){
                    seg.modify(1, n, l, curr, -l + curl, 1);
                }
            }
            iter = upper_bound(rngs[i].begin(), rngs[i].end(), make_pair(r, n + 1));
            if(iter != rngs[i].begin()){
                auto &[curl, curr] = (*prev(iter));
                if(curr > r){
                    seg.modify(1, n, curl, r, -curr + r, 1);
                }
            }
        }
        ans[hey] = 20ll * (r - l + 1) - seg.query(1, n, l, r, 1);
        for(int i = 1; i < 20; i++){
            auto iter = lower_bound(rngs[i].begin(), rngs[i].end(), make_pair(l, 0));
            if(iter != rngs[i].begin()){
                auto &[curl, curr] = (*prev(iter));
                if(l <= curr){
                    seg.modify(1, n, l, curr, l - curl, 1);
                }
            }
            iter = upper_bound(rngs[i].begin(), rngs[i].end(), make_pair(r, n + 1));
            if(iter != rngs[i].begin()){
                auto &[curl, curr] = (*prev(iter));
                if(curr > r){
                    seg.modify(1, n, curl, r, curr - r, 1);
                }
            }
        }
    }
    return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp meetings.cpp

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