Submission #681549

#	Time	Username	Problem	Language	Result	Execution time	Memory
681549		vinnipuh01	Examination (JOI19_examination)	C++17	100 / 100	649 ms	43976 KiB

examination

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define sqrt sqrtl

 
using namespace std;

const long long oo = 1000000000000000000;
 
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
 
 
/*
    ViHHiPuh
 
   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))
 
 
    cout << fixed << setprecision(6) << x;
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    freopen ( "sum.in", "r", stdin )
*/


int n, m, a[ 100001 ], b[ 100001 ], x[ 100001 ], y[ 100001 ], z[ 100001 ];
int t[ 1600001 ], tt[ 1600001 ], t1[ 1600001 ];
int an[ 100001 ];

void upd( int v, int tl, int tr, int pos ) {
	if ( tl > pos || tr < pos )
		return;
	if ( tl == tr ) {
		t[ v ] ++;
		return;
	}
	int mid = ( tl + tr ) / 2;
	upd( v + v, tl, mid, pos );
	upd( v + v + 1, mid + 1, tr, pos );
	t[ v ] = t[ v + v  ] + t[ v + v + 1 ];
}

void updd( int v, int tl, int tr, int pos ) {
	if ( tl > pos || tr < pos )
		return;
	if ( tl == tr ) {
		tt[ v ] ++;
		return;
	}
	int mid = ( tl + tr ) / 2;
	updd( v + v, tl, mid, pos );
	updd( v + v + 1, mid + 1, tr, pos );
	tt[ v ] = tt[ v + v ] + tt[ v + v + 1 ];
}

void gett( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		sum -= t[ v ];
		return;
	}
	int mid = ( tl + tr ) / 2;
	gett( v + v, tl, mid, l, r );
	gett( v + v + 1, mid + 1, tr, l, r );
}

void get1( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		sum -= tt[ v ];
		return;
	} 
	int mid = ( tl + tr ) / 2;
	get1( v + v, tl, mid, l, r );
	get1( v + v +1, mid +1 , tr, l, r );
}

void upd1( int v, int tl, int tr, int pos ) {
	if ( tl > pos || tr < pos )
		return;
	if ( tl == tr ) {
		t1[ v ] ++;
		return;
	}
	int mid = ( tl + tr ) / 2;
	upd1( v + v, tl, mid, pos );
	upd1( v + v + 1, mid + 1, tr, pos );
	t1[ v ] = t1[ v + v ] + t1[ v + v + 1 ];
}

void gett1( int v, int tl, int tr, int l, int r ) {
	if ( tl > r || tr < l )
		return;
	if ( tl >= l && tr <= r ) {
		sum += t1[ v ];
		return;
	} 
	int mid = ( tl + tr ) / 2;
	gett1( v + v, tl, mid, l, r );
	gett1( v + v + 1, mid + 1, tr, l, r );
}

vector <int> V;
vector <pair<int, int> > v, v1, v2, vv;

map <int, int> mp;

main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for ( int i = 1; i <= n; i ++ ) {
		cin >> a[ i ] >> b[ i ];
		V.push_back( a[ i ] );
		V.push_back( b[ i ] );
		v.push_back( { a[ i ] + b[ i ], i } );
	} 
	for ( int i = 1; i <= m; i ++ ) {
		cin >> x[ i ] >> y[ i ] >> z[ i ];
		V.push_back( x[ i ] );
		V.push_back( y[ i ] );
	}
	sort( v.begin(), v.end() );
	sort( V.begin(), V.end() );
	for ( auto i : V ) {
		if ( !mp[ i ] )
			mp[ i ] = ++num;
	}
	for ( int i = 1; i <= n; i ++ ) {
		a[ i ] = mp[ a[ i ] ], b[ i ] = mp[ b[ i ] ];
		vv.push_back( { a[ i ], i } );
	}
	sort( vv.begin(), vv.end() );
	reverse( vv.begin(), vv.end() );
	for ( int i = 1; i <= m; i ++ ) {
		if ( x[ i ] + y[ i ] < z[ i ] )
			v1.push_back( { z[ i ], i } );
		else {
			v2.push_back( { mp[ x[ i ] ], i } );
		}
		x[ i ] = mp[ x[ i ] ];
		y[ i ] = mp[ y[ i ] ];
	}
	sort( v1.begin(), v1.end() );
	reverse( v1.begin(), v1.end() );
	reverse( v.begin(), v.end() );
	for ( auto i : v1 ) {
		while ( pos < v.size() && v[ pos ].first >= i.first ) {
			upd( 1, 1, num, a[ v[ pos ].second ] );
			updd( 1, 1, num, b[ v[ pos ].second ] );
			pos ++;
		}
//		cout << i.second << " - ";
		sum = pos;
		if ( x[ i.second ] != 1 )
			gett( 1, 1, num, 1, x[ i.second ] - 1 );
//		cout << sum << " ";
		if ( y[ i.second ] != 1 )
			get1( 1, 1, num, 1, y[ i.second ] - 1 );
//		cout << sum << "\n";
		an[ i.second ] = sum;
	}
	sort( v2.begin(), v2.end() );
	reverse( v2.begin(), v2.end() );
	pos = 0;
	for ( auto i : v2 ) {
		while ( pos < v.size() && vv[ pos ].first >= i.first ) {
			upd1( 1, 1, num, b[ vv[ pos ].second ] );
			pos ++;
		}
		sum = 0;
		gett1( 1, 1, num, y[ i.second ], num );
		an[ i.second ] = sum;
	}
	for ( int i = 1; i <= m; i ++ )
		cout << an[ i ] << "\n";
}

Compilation message (stderr)

examination.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  132 | main () {
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:172:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |   while ( pos < v.size() && v[ pos ].first >= i.first ) {
      |           ~~~~^~~~~~~~~~
examination.cpp:191:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   while ( pos < v.size() && vv[ pos ].first >= i.first ) {
      |           ~~~~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57