#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std ;
#define MAXN 200007
int n , q ;
int a[ MAXN ] ;
int b[ MAXN ] ;
int x[ MAXN ] ;
int lst[ MAXN ] ;
pair < int , int > srt[ MAXN ] ;
vector < pair < int , int > > v ;
class DumbTree {
public :
int tr[ 3 * MAXN ] ;
void init ( int where , int IL , int IR ) {
tr[ where ] = 0 ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
void update ( int where , int IL , int IR , int pos ) {
if ( IL == IR ) {
tr[ where ] = x[ IL ] ;
return ;
}
int mid = ( IL + IR ) / 2 ;
if ( pos <= mid ) {
update ( 2 * where , IL , mid , pos ) ;
}
else {
update ( 2 * where + 1 , mid + 1 , IR , pos ) ;
}
tr[ where ] = max ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}
int find ( int where , int IL , int IR , int sr ) {
if ( tr[ where ] < sr ) { return 0 ; }
if ( IL == IR ) { return IL ; }
int mid = ( IL + IR ) / 2 ;
if ( tr[ 2 * where + 1 ] >= sr ) {
return find ( 2 * where + 1 , mid + 1 , IR , sr ) ;
}
return find ( 2 * where , IL , mid , sr ) ;
}
};
DumbTree u ;
class Tree {
public :
vector < int > tr[ 3 * MAXN ] ;
void merge ( int where ) {
int sz1 = tr[ 2 * where ].size ( ) ;
int sz2 = tr[ 2 * where + 1 ].size ( ) ;
int pos1 , pos2 ;
pos1 = pos2 = 0 ;
while ( pos1 != sz1 || pos2 != sz2 ) {
if ( pos2 == sz2 ) {
tr[ where ].push_back ( tr[ 2 * where ][ pos1 ] ) ;
pos1 ++ ;
}
else if ( pos1 == sz1 ) {
tr[ where ].push_back ( tr[ 2 * where + 1 ][ pos2 ] ) ;
pos2 ++ ;
}
else {
if ( tr[ 2 * where ][ pos1 ] < tr[ 2 * where + 1 ][ pos2 ] ) {
tr[ where ].push_back ( tr[ 2 * where ][ pos1 ] ) ;
pos1 ++ ;
}
else {
tr[ where ].push_back ( tr[ 2 * where + 1 ][ pos2 ] ) ;
pos2 ++ ;
}
}
}
}
void init ( int where , int IL , int IR ) {
if ( IL == IR ) {
tr[ where ].push_back ( x[ IL ] ) ;
return ;
}
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
merge ( where ) ;
}
int bin ( int where , int sr ) {
int l , r , mid ;
l = 0 ;
r = tr[ where ].size ( ) - 1 ;
if ( tr[ where ][ 0 ] >= sr ) { return ( r + 1 ) ; }
if ( tr[ where ][ r ] < sr ) { return 0 ; }
while ( ( r - l ) > 3 ) {
mid = ( l + r ) / 2 ;
if ( tr[ where ][ mid ] >= sr ) { r = mid ; }
else { l = mid ; }
}
while ( tr[ where ][ l ] < sr ) { l ++ ; }
return ( tr[ where ].size ( ) - l ) ;
}
int query ( int where , int IL , int IR , int pos , int sr ) {
if ( IL > IR ) { return 0 ; }
if ( IR < pos ) { return 0 ; }
if ( pos <= IL ) {
return bin ( where , sr ) ;
}
int mid = ( IL + IR ) / 2 ;
return ( query ( 2 * where , IL , mid , pos , sr ) + query ( 2 * where + 1 , mid + 1 , IR , pos , sr ) ) ;
}
};
Tree w ;
void input ( ) {
scanf ( "%d%d" , &n , &q ) ;
int i ;
for ( i = 1 ; i <= n ; i ++ ) {
scanf ( "%d%d" , &a[ i ] , &b[ i ] ) ;
v.push_back ( make_pair ( max ( a[ i ] , b[ i ] ) , i ) ) ;
}
for ( i = 1 ; i <= q ; i ++ ) {
scanf ( "%d" , &x[ i ] ) ;
srt[ i ] = make_pair ( x[ i ] , i ) ;
}
sort ( v.begin ( ) , v.end ( ) ) ;
sort ( srt + 1 , srt + q + 1 ) ;
}
void solve ( ) {
u.init ( 1 , 1 , q ) ;
int i , pos ;
pos = 1 ;
for ( i = 0 ; i < n ; i ++ ) {
while ( pos <= n && srt[ pos ].first < v[ i ].first ) {
u.update ( 1 , 1 , q , srt[ pos ].second ) ;
pos ++ ;
}
lst[ v[ i ].second ] = u.find ( 1 , 1 , q , min ( a[ v[ i ].second ] , b[ v[ i ].second ] ) ) ;
}
w.init ( 1 , 1 , q ) ;
long long ans = 0 ;
for ( i = 1 ; i <= n ; i ++ ) {
int br = w.query ( 1 , 1 , q , lst[ i ] + 1 , a[ i ] ) ;
if ( lst[ i ] != 0 ) {
if ( a[ i ] < b[ i ] ) { swap ( a[ i ] , b[ i ] ) ; }
}
if ( ( br % 2 ) == 1 ) {
swap ( a[ i ] , b[ i ] ) ;
}
ans += a[ i ] ;
}
printf ( "%lld\n" , ans ) ;
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
Compilation message
fortune_telling2.cpp: In function 'void input()':
fortune_telling2.cpp:127:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d" , &n , &q ) ;
^
fortune_telling2.cpp:130:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d" , &a[ i ] , &b[ i ] ) ;
^
fortune_telling2.cpp:134:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d" , &x[ i ] ) ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
24668 KB |
Output is correct |
| 2 |
Correct |
33 ms |
26380 KB |
Output is correct |
| 3 |
Correct |
69 ms |
27012 KB |
Output is correct |
| 4 |
Correct |
73 ms |
29804 KB |
Output is correct |
| 5 |
Correct |
76 ms |
29804 KB |
Output is correct |
| 6 |
Correct |
73 ms |
29804 KB |
Output is correct |
| 7 |
Correct |
83 ms |
29804 KB |
Output is correct |
| 8 |
Correct |
69 ms |
29804 KB |
Output is correct |
| 9 |
Correct |
53 ms |
29804 KB |
Output is correct |
| 10 |
Correct |
63 ms |
29804 KB |
Output is correct |
| 11 |
Correct |
59 ms |
29804 KB |
Output is correct |
| 12 |
Correct |
46 ms |
29804 KB |
Output is correct |
| 13 |
Incorrect |
103 ms |
29804 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
269 ms |
52308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
