oj.uz

답안 #954779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954779 2024-03-28T14:22:25 Z LucaIlie Measures (CEOI22_measures) C++17
0 / 100
 291 ms 51272 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5;
const long long INF = 1e15;
int x[MAX_N], nrm[MAX_N];
map<int, vector<int>> frecv;

struct SegTree1 {
    int leftQuery, rightQuery;
    long long segTree[4 * MAX_N], lazy[4 * MAX_N];

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void init( int v, int l, int r ) {
        if ( l == r ) {
            segTree[v] = INF;
            return;
        }
        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
        segTree[v] = min( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }
    void init( int l, int r ) {
        leftQuery = l;
        rightQuery = r;
        init( 0, l, r );
    }

    void update( int v, int l, int r, int lu, int ru, long long x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = min( segTree[v * 2 + 1], segTree[v * 2 + 2] );
        //printf( "%d %d %lld %lld\n", l, r, segTree[v].minn, segTree[v].maxx );
    }
    void update( int l, int r, long long x ) {
        //printf( "U %d %d %lld\n", l, r, x );
        update( 0, leftQuery, rightQuery, l, r, x );
    }

    long long queryMaxAll() {
        return segTree[0];
    }
} costMin

;struct SegTree {
    int leftQuery, rightQuery;
    long long segTree[4 * MAX_N], lazy[4 * MAX_N];

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void init( int v, int l, int r ) {
        if ( l == r ) {
            segTree[v] = -INF;
            return;
        }
        int mid = (l + r) / 2;
        init( v * 2 + 1, l, mid );
        init( v * 2 + 2, mid + 1, r );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }
    void init( int l, int r ) {
        leftQuery = l;
        rightQuery = r;
        init( 0, l, r );
    }

    void update( int v, int l, int r, int lu, int ru, long long x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
        //printf( "%d %d %lld %lld\n", l, r, segTree[v].minn, segTree[v].maxx );
    }
    void update( int l, int r, long long x ) {
        //printf( "U %d %d %lld\n", l, r, x );
        update( 0, leftQuery, rightQuery, l, r, x );
    }

    long long queryMaxAll() {
        return segTree[0];
    }
} costMax;

int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );

    int n, q, d;

    cin >> n >> q >> d;

    n += q;
    for ( int i = 0; i < n; i++ ) {
        cin >> x[i];
        frecv[x[i]].push_back( i );
    }

    int val = 0;
    for ( auto p: frecv ) {
        for ( int i: p.second )
            nrm[i] = ++val;
    }

    costMin.init( 1, n );
    costMax.init( 1, n );
    for ( int i = 0; i < n; i++ ) {
        costMin.update( nrm[i], n, d );
        costMax.update( nrm[i], n, d );
        costMin.update( nrm[i], nrm[i], -INF - x[i] );
        costMax.update( nrm[i], nrm[i], INF - x[i] );

        if ( i >= n - q ) {
            long long ans = costMax.queryMaxAll() - costMin.queryMaxAll();
            cout << ans / 2;
            if ( ans % 2 == 1 )
                cout << ".5";
            cout << " ";
        }
    }

    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 291 ms 51272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 291 ms 51272 KB Output isn't correct
2 Halted 0 ms 0 KB -