Submission #33044

#	Time	Username	Problem	Language	Result	Execution time	Memory
33044		chonka	Star triangles (IZhO11_triangle)	C++98	100 / 100	396 ms	10292 KiB

triangle

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<map>
using namespace std ;

#define MAXN 300007

int n ;
pair < int , int > a[ MAXN ] ;

map < int , int > ZX ;

int h[ MAXN ] ;
int v[ MAXN ] ;

void compress ( ) {
    vector < int > srt ;
    srt.clear ( ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        srt.push_back ( a[ i ].first ) ;
    }

    sort ( srt.begin ( ) , srt.end ( ) ) ;
    int id = 1 ;
    ZX.clear ( ) ;
    ZX[ srt[ 0 ] ] = 1 ;
    for ( i = 1 ; i < n ; i ++ ) {
        if ( srt[ i ] == srt[ i - 1 ] ) { continue ; }
        id ++ ;
        ZX[ srt[ i ] ] = id ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        a[ i ].first = ZX[ a[ i ].first ] ;
        v[ a[ i ].first ] ++ ;
    }
    srt.clear ( ) ;
    ZX.clear ( ) ;
    id = 1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        srt.push_back ( a[ i ].second ) ;
    }

    sort ( srt.begin ( ) , srt.end ( ) ) ;
    ZX[ srt[ 0 ] ] = 1 ;
    for ( i = 1 ; i < n ; i ++ ) {
        if ( srt[ i ] == srt[ i - 1 ] ) { continue ; }
        id ++ ;
        ZX[ srt[ i ] ] = id ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        a[ i ].second = ZX[ a[ i ].second ] ;
        h[ a[ i ].second ] ++ ;
    }
}

void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d%d" , &a[ i ].first , &a[ i ].second ) ;
    }
    compress ( ) ;
}

void solve ( ) {
    long long ans = 0 ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        ans += 1LL * ( v[ a[ i ].first ] - 1 ) * ( h[ a[ i ].second ] - 1 ) ;
    }
    printf ( "%lld\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

triangle.cpp: In function 'void input()':
triangle.cpp:60:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
triangle.cpp:63:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d" , &a[ i ].first , &a[ i ].second ) ;
                                                           ^

• Subtask 1: 100 / 100