Submission #1165406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165406		KG07	Meetings (IOI18_meetings)	C++20	0 / 100	41 ms	23748 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

struct segment_tree{
    int L[800000], R[800000], n;
    int t[2100000], T[2100000], root;
    long long a[2100000], b[2100000], c[2100000], A[2100000], B[2100000], C[2100000], S[800000];
    vector<pair<int, pair<int, int>>> Q[800000];
    stack<int> s;
    queue<int> q;
    void init(int N, int M, vector<int> H, vector<int> X, vector<int> Y){
        n = N;
        for(int i = 0; i < N; i++)q.push(H[i]);
        create_tree(1, 1, N);
        for(int i = 0; i < N; i++){
            while(!s.empty() && H[s.top()] < H[i]){
                int h = s.top();
                s.pop();
                if(!s.empty() && H[s.top()] < H[i])R[s.top()+1] = h+1;
                else L[i+1] = h+1;
            }
            s.push(i);
        }
        while(!s.empty()){
            int h = s.top();
            s.pop();
            if(!s.empty())R[s.top()+1] = h+1;
            else root = h+1;
        }
        for(int i = 0; i < M; i++)Q[find_root(X[i], Y[i])].push_back(make_pair(i, make_pair(X[i]+1, Y[i]+1)));
    }
    void create_tree(int N, int l, int r){
        if(l == r){
            t[N] = q.front();
            T[N] = r;
            a[N] = q.front();
            A[N] = q.front();
            q.pop();
            return;
        }
        create_tree(2*N, l, (l+r)/2);
        create_tree(2*N+1, (l+r)/2+1, r);
        a[N] = a[2*N];
        A[N] = A[2*N+1];
        t[N] = max(t[2*N], t[2*N+1]);
        T[N] = t[N]==t[2*N]?T[2*N]:T[2*N+1];
    }
    int get_maximum(int N, int x, int y, int *z, int l, int r){
        if(x > r || y < l)return 0;
        if(x <= l && y >= r){
            if(t[N] > *z){
                *z = t[N];
                return T[N];
            }
            return 0;
        }
        int X = get_maximum(2*N, x, y, z, l, (l+r)/2);
        int h = *z;
        int Y = get_maximum(2*N+1, x, y, z, (l+r)/2+1, r);
        if(h >= *z)return X;
        return Y;
    }
    int find_root(int x, int y){
        int z = 0;
        return get_maximum(1, x+1, y+1, &z, 1, n);
    }
    void lazy_left(int N, int l, int r){
        if(l==r){
            b[N]=0;
            c[N]=0;
            return;
        }
        if(b[N]){
            b[2*N] = b[N];
            b[2*N+1] = b[N];
            a[2*N] = a[N];
            a[2*N+1] = a[N] + b[N]*((r-l)/2+1);
            b[N] = 0;
            c[N] = 0;
        }
        a[2*N] += c[N];
        c[2*N] += c[N];
        a[2*N+1] += c[N];
        c[2*N+1] += c[N];
        c[N] = 0;
    }
    void lazy_right(int N, int l, int r){
        if(l==r){
            B[N]=0;
            C[N]=0;
            return;
        }
        if(B[N]){
            B[2*N] = B[N];
            B[2*N+1] = B[N];
            A[2*N] = A[N] + B[N]*((r-l+1)/2);
            A[2*N+1] = A[N];
            B[N] = 0;
            C[N] = 0;
        }
        A[2*N] += C[N];
        C[2*N] += C[N];
        A[2*N+1] += C[N];
        C[2*N+1] += C[N];
        C[N] = 0;
    }
    long long get_left(int N, int x, int l, int r){
        if(b[N])return a[N]+b[N]*(x-l);
        if(l == r)return a[N];
        lazy_left(N, l, r);
        if(x > (l+r)/2)return get_left(2*N+1, x, (l+r)/2+1, r);
        return get_left(2*N, x, l, (l+r)/2);
    }
    long long get_right(int N, int x, int l, int r){
        if(B[N])return A[N]+B[N]*(r-x);
        if(l == r)return A[N];
        lazy_right(N, l, r);
        if(x > (l+r)/2)return get_right(2*N+1, x, (l+r)/2+1, r);
        return get_right(2*N, x, l, (l+r)/2);
    }
    void add_left(int N, int x, int y, long long z, int l, int r){
        if(x > r || y < l)return;
        if(x <= l && y >= r){
            c[N] += z;
            a[N] += z;
            return;
        }
        lazy_left(N, l, r);
        add_left(2*N, x, y, z, l, (l+r)/2);
        add_left(2*N+1, x, y, z, (l+r)/2+1, r);
    }
    void add_right(int N, int x, int y, long long z, int l, int r){
        if(x > r || y < l)return;
        if(x <= l && y >= r){
            C[N] += z;
            A[N] += z;
            return;
        }
        lazy_right(N, l, r);
        add_right(2*N, x, y, z, l, (l+r)/2);
        add_right(2*N+1, x, y, z, (l+r)/2+1, r);
    }
    void set_left(int N, int x, int y, long long z, long long Z, int l, int r){
        if(x > r || y < l)return;
        if(x <= l && y >= r){
            a[N] = z+Z*(l-x);
            b[N] = Z;
            return;
        }
        lazy_left(N, l, r);
        set_left(2*N, x, y, z, Z, l, (l+r)/2);
        set_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
    }
    void set_right(int N, int x, int y, long long z, long long Z, int l, int r){
        if(x > r || y < l)return;
        if(x <= l && y >= r){
            A[N] = z+Z*(y-r);
            B[N] = Z;
            return;
        }
        lazy_right(N, l, r);
        set_right(2*N, x, y, z, Z, l, (l+r)/2);
        set_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
    }
    int find_left(int N, int x, int y, long long z, long long Z, int l, int r){
        if(x > r || y < l)return 0;
        lazy_left(N, l, r);
        if(x <= l){
            if(Z * (l-x+1) - a[N] > z)return 0;
            if(l == r)return r;
            int k = find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
            if(k)return k;
            return find_left(2*N, x, y, z, Z, l, (l+r)/2);
        }
        if(x > (l+r)/2)return find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
        if(y < (l+r)/2+1)return find_left(2*N, x, y, z, Z, l, (l+r)/2);
        int k = find_left(2*N+1, x, y, z, Z, (l+r)/2+1, r);
        if(k)return k;
        return find_left(2*N, x, y, z, Z, l, (l+r)/2);
    }
    int find_right(int N, int x, int y, long long z, long long Z, int l, int r){
        if(x > r || y < l)return 0;
        lazy_right(N, l, r);
        if(y >= r){
            if(Z * (y-r+1) - A[N] > z)return 0;
            if(l == r)return r;
            int k = find_right(2*N, x, y, z, Z, l, (l+r)/2);
            if(k)return k;
            return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
        }
        if(x > (l+r)/2)return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
        if(y < (l+r)/2+1)return find_right(2*N, x, y, z, Z, l, (l+r)/2);
        int k = find_right(2*N, x, y, z, Z, l, (l+r)/2);
        if(k)return k;
        return find_right(2*N+1, x, y, z, Z, (l+r)/2+1, r);
    }
    void merge(int N, int l, int r){
        if(L[N])merge(L[N], l, N-1);
        if(R[N])merge(R[N], N+1, r);
        long long X = get_left(1, r, 1, n);
        long long Y = get_right(1, l, 1, n);
        int Z = 0;
        get_maximum(1, N, N, &Z, 1, n);
        for(int i = 0; i < Q[N].size(); i++){
            if(Q[N][i].second.first == N && Q[N][i].second.second == N){
                S[Q[N][i].first] = Z;
                continue;
            }
            if(Q[N][i].second.first == N){
                S[Q[N][i].first] = Z+get_left(1, Q[N][i].second.second, 1, n);
                continue;
            }
            if(Q[N][i].second.second == N){
                S[Q[N][i].first] = Z+get_right(1, Q[N][i].second.first, 1, n);
                continue;
            }
            S[Q[N][i].first] = Z*(Q[N][i].second.second-Q[N][i].second.first+1)-max(Z*(N-Q[N][i].second.first)-get_right(1, Q[N][i].second.first, 1, n), Z*(Q[N][i].second.second-N)-get_left(1, Q[N][i].second.second, 1, n));
        }
        if(l < N)add_left(1, N, N, Y, 1, n);
        if(r > N)add_right(1, N, N, X, 1, n);
        if(!L[N] && !R[N])return;
        if(!L[N]){
            add_left(1, N+1, r, Z, 1, n);
            return;
        }
        if(!R[N]){
            add_right(1, l, N-1, Z, 1, n);
            return;
        }
        int z;
        z = find_left(1, N+1, r, 1LL*Z*(N-l)-Y, Z, 1,n);
        if(z){
            set_left(1, N+1, z, Y+Z*2, Z, 1, n);
            if(z<r)add_left(1, z+1, r, Z*(N-l+1), 1, n);
        }
        else add_left(1, N+1, r, Z*(N-l+1), 1, n);
        z = find_right(1, l, N-1, 1LL*Z*(r-N)-X, Z, 1, n);
        if(z){
            set_right(1, z, N-1, X+Z*2, Z, 1, n);
            if(z>l)add_right(1, l, z-1, Z*(N-l+1), 1, n);
        }
        else add_right(1, l, N-1, Z*(N-l+1), 1, n);
    }
} A;

vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    int N = H.size();
    int Q = R.size();
    A.init(N, Q, H, L, R);
    A.merge(A.root, 1, A.n);
    vector<long long> Z;
    for(int i = 0; i < Q; i++)Z.push_back(A.S[i]);
    return Z;
}

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