oj.uz

Submission #104019

# Submission time Handle Problem Language Result Execution time Memory
104019 2019-04-03T17:11:39 Z DiegoGarcia Sails (IOI07_sails) C++14
40 / 100
 1000 ms 34424 KB 
#include <bits/stdc++.h>
#define optimiza_io ios_base::sync_with_stdio(false); cin.tie(0);
#define ft first
#define sd second
#define ll long long
#define pb push_back
#define INF 1E18
using namespace std;

const int maxn = 1e5+3;
int n;
ll ans;

struct s{
    ll h, k;
}sail[maxn];

bool cmp( const s &a, const s &b )
{
    if( a.h == b.h ) return a.k < b.k;
    return a.h < b.h;
}

struct stnode
{
    ll maxi;
    ll mini;
    ll sum;
    ll lazy_add;
    ll lazy_change = -1;
}st[8*maxn]; //maxn = maxh, meh

int mypos, endpos, startpos, lpt;
ll mio, quiero, maxh = 0;

inline void push( int nodo, int l, int r )
{
    int md = (l+r)/2;
    if( st[nodo].lazy_change != -1 )
    {
        if( l != r )
        {
            push( 2*nodo+1, l, md );
            push( 2*nodo+2, md+1, r );
            st[2*nodo+1].lazy_change = st[2*nodo+2].lazy_change = st[nodo].lazy_change;
        }
        st[nodo].maxi = st[nodo].mini = st[nodo].lazy_change;
        st[nodo].sum = (r-l+1)*st[nodo].lazy_change;
        st[nodo].lazy_add = 0;
        st[nodo].lazy_change = -1;
    }
    else if( st[nodo].lazy_add )
    {
        if( l != r )
        {
            push( 2*nodo+1, l, md );
            push( 2*nodo+2, md+1, r );
            st[2*nodo+1].lazy_add += st[nodo].lazy_add;
            st[2*nodo+2].lazy_add += st[nodo].lazy_add;
        }
        st[nodo].maxi += st[nodo].lazy_add;
        st[nodo].mini += st[nodo].lazy_add;
        st[nodo].sum += (r-l+1)*st[nodo].lazy_add;
        st[nodo].lazy_add = 0;
    }
    return;
}

ll getsum( int nodo, int l, int r, int sq, int eq )
{
    push( nodo, l, r );
    if( l > eq || r < sq )return 0;
    if( l >= sq && r <= eq ){
        return st[nodo].sum;
    }
    int md = (l+r)/2;
    return ( getsum(2*nodo+1, l, md, sq, eq ) + getsum( 2*nodo+2, md+1, r, sq, eq ) );
}

pair<int,ll> ultimo( int nodo, int l, int r, int p ) //posicion, valor
{
    push( nodo, l, r );
    if( r < p ) return {-1,-1};
    int md = (l+r)/2;
    if( l >= p )
    {
        if( l == r ){
            return { st[nodo].maxi, l };
        }

        push( 2*nodo+2, md+1, r );
        if( st[2*nodo+2].mini <= quiero ){
            return ultimo( 2*nodo+2, md+1, r, p );
        }
        return ultimo( 2*nodo+1, l, md, p );
    }
    auto rchild = ultimo( 2*nodo+2, md+1, r, p );
    if( rchild.ft == quiero ){;
        return rchild;
    }
    return ultimo( 2*nodo+1, l, md, p );
}

pair <int,ll> primero( int nodo, int l, int r, int p ) //posicion, valor
{
    push( nodo, l, r );
    if( r < p ){
        return {-1,-1};
    }
    int md = (l+r)/2;
    if( l >= p )
    {
        if( l == r ){
            return { st[nodo].maxi, l };
        }
        push( 2*nodo+1, l, md );
        if( st[2*nodo+1].maxi >= quiero ){
            return primero( 2*nodo+1, l, md, p );
        }
        return primero( 2*nodo+2, md+1, r, p );
    }

    auto lchild = primero( 2*nodo+1, l, md, p );
    if( lchild.ft == quiero ){
        return lchild;
    }
    return primero( 2*nodo+2, md+1, r, p );
}

void change( int nodo, int l, int r, int sq, int eq, ll val )
{
    push( nodo, l, r );
    int md = (l+r)/2;
    if( l >= sq && r <= eq )
    {
        st[nodo].mini = st[nodo].maxi = val;
        st[nodo].sum = (r-l+1)*val;
        if( l != r )
        {
            push( 2*nodo+1, l, md );
            push( 2*nodo+2, md+1, r );
            st[2*nodo+1].lazy_change = val;
            st[2*nodo+2].lazy_change = val;
        }
        return;
    }
    if( l > eq || r < sq ) return;
    change( 2*nodo+1, l, md, sq, eq, val );
    change( 2*nodo+2, md+1, r, sq, eq, val );
    st[nodo].sum = st[2*nodo+1].sum + st[2*nodo+2].sum;
    st[nodo].mini = min( st[2*nodo+1].mini, st[2*nodo+2].mini );
    st[nodo].maxi = max( st[2*nodo+1].maxi, st[2*nodo+2].maxi );
    return;
}

void add( int nodo, int l, int r, int sq, int eq, ll val )
{
    push( nodo, l, r );
    int md = (l+r)/2;
    if( l >= sq && r <= eq )
    {
        st[nodo].mini += val;
        st[nodo].maxi += val;
        st[nodo].sum += (r-l+1)*val;
        if( l != r )
        {
            push( 2*nodo+1, l, md );
            push( 2*nodo+2, md+1, r );
            st[2*nodo+1].lazy_add += val;
            st[2*nodo+2].lazy_add += val;
        }
        return;
    }
    if( l > eq || r < sq ) return;
    add( 2*nodo+1, l, md, sq, eq, val );
    add( 2*nodo+2, md+1, r, sq, eq, val );

    st[nodo].sum = st[2*nodo+1].sum + st[2*nodo+2].sum;
    st[nodo].mini = min( st[2*nodo+1].mini, st[2*nodo+2].mini );
    st[nodo].maxi = max( st[2*nodo+1].maxi, st[2*nodo+2].maxi );
    return;
}

int main()
{
    optimiza_io
    cin >> n;
    for( int i=0; i<n; i++ ){
        cin >> sail[i].h >> sail[i].k;
        maxh = max( sail[i].h, maxh );
    }
    sort( sail, sail + n, cmp );
    for( int i=0; i<n; i++ )
    {
        lpt = maxh - sail[i].h + 1;
        mypos = lpt + sail[i].k - 1;
        mio = getsum( 0, 1, maxh, lpt, mypos );
        ans += mio;

        quiero = getsum( 0, 1, maxh, mypos, mypos );

        endpos = ultimo( 0, 1, maxh, mypos ).sd;

        startpos = primero( 0, 1, maxh, lpt ).sd;

        add( 0, 1, maxh, lpt, mypos, 1 );

        int grandes = mypos - startpos + 1;
        int resto = endpos - startpos + 1 - grandes;

            if( startpos+resto-1>=startpos  ){
                change( 0, 1, maxh, startpos, startpos+resto-1, quiero );
            }
            if( startpos+resto <= endpos ){
                change( 0, 1, maxh, startpos+resto, endpos, quiero + 1 );
            }
    }
    cout << ans;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31616 KB Output is correct
2 Correct 24 ms 31616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31616 KB Output is correct
2 Correct 24 ms 31612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31616 KB Output is correct
2 Correct 34 ms 31744 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31740 KB Output is correct
2 Correct 444 ms 31716 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 31864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 32376 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 32888 KB Time limit exceeded

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 33628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 34040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 34424 KB Time limit exceeded
2 Halted 0 ms 0 KB -