oj.uz

Submission #681010

# Submission time Handle Problem Language Result Execution time Memory
681010 2023-01-12T08:52:51 Z vinnipuh01 Examination (JOI19_examination) C++17
20 / 100
 358 ms 19268 KB 
#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 int long long
#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, x, y, a[ 100001 ], b[ 100001 ], c[ 100001 ], an[ 100001 ], t[ 1000001 ];

map <int, int> mp;

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

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 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 );
}

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

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 16544 KB Output is correct
2 Correct 358 ms 18760 KB Output is correct
3 Correct 332 ms 18712 KB Output is correct
4 Correct 190 ms 14504 KB Output is correct
5 Correct 201 ms 15516 KB Output is correct
6 Correct 77 ms 9864 KB Output is correct
7 Correct 297 ms 18840 KB Output is correct
8 Correct 285 ms 18668 KB Output is correct
9 Correct 298 ms 18592 KB Output is correct
10 Correct 181 ms 15520 KB Output is correct
11 Correct 183 ms 14368 KB Output is correct
12 Correct 58 ms 9476 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 16544 KB Output is correct
2 Correct 358 ms 18760 KB Output is correct
3 Correct 332 ms 18712 KB Output is correct
4 Correct 190 ms 14504 KB Output is correct
5 Correct 201 ms 15516 KB Output is correct
6 Correct 77 ms 9864 KB Output is correct
7 Correct 297 ms 18840 KB Output is correct
8 Correct 285 ms 18668 KB Output is correct
9 Correct 298 ms 18592 KB Output is correct
10 Correct 181 ms 15520 KB Output is correct
11 Correct 183 ms 14368 KB Output is correct
12 Correct 58 ms 9476 KB Output is correct
13 Incorrect 323 ms 19268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -