oj.uz

Submission #134121

# Submission time Handle Problem Language Result Execution time Memory
134121 2019-07-22T06:01:45 Z DodgeBallMan Sails (IOI07_sails) C++14
100 / 100
 113 ms 2796 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;
int fen[N], n, mh;
long long ans;
vector<pii> v;

void up( int l, int r ) {
    if( l > r ) return ;
    for( int i = l ; i < N ; i += ( i & -i ) ) fen[i] += 1;
    for( int i = r + 1 ; i < N ; i += ( i & -i ) ) fen[i] += -1;
}

int query( int x ) {
    int ret = 0;
    for( int i = x ; i > 0 ; i -= ( i & -i ) ) ret += fen[i];
    return ret;
}

int main()
{
    scanf("%d",&n);
    for( int i = 1, h, k ; i <= n ; i++ ) {
        scanf("%d %d",&h,&k);
        mh = max( mh, h );
        v.emplace_back( pii( h, k ) );
    }
    sort( v.begin(), v.end() );
   // printf("\n");
    for( int i = 0 ; i < ( int )v.size() ; i++ ) {
        int x = v[i].x - v[i].y + 1;
        int t = query( x ), l = 1, r = v[i].x, lb, rb;
        while( l < r ) {
            int mid = ( l + r + 1 ) >> 1;
            if( query( mid ) >= t ) l = mid;
            else r = mid - 1;
        }
        rb = l;
        l = 1, r = v[i].x;
        while( l < r ) {
            int mid = ( l + r ) >> 1;
            if( query( mid ) <= t ) r = mid;
            else l = mid + 1;
        }
        lb = l;
        int temp = min( v[i].x, rb ) - max( x, lb ) + 1;
        up( rb + 1, rb + v[i].y - temp ), up( lb, lb + temp - 1 );
        //printf("%d %d %d %d %d %d %d\n",lb,rb,temp,v[i].x,v[i].y,x,t);
    }
    for( int i = 1 ; i <= mh ; i++ ) {
        long long x = ( long long )query( i );
        //printf("%lld ",x);
        ans += ( x - 1 ) * x / 2;
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
sails.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&h,&k);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 680 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 24 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1648 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2516 KB Output is correct
2 Correct 76 ms 2516 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2664 KB Output is correct
2 Correct 72 ms 2288 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 2796 KB Output is correct
2 Correct 65 ms 2416 KB Output is correct