Submission #333078

#	Time	Username	Problem	Language	Result	Execution time	Memory
333078		CaroLinda	Examination (JOI19_examination)	C++14	100 / 100	2945 ms	297764 KiB

examination

#include <bits/stdc++.h>

#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

const int MAXN = 4e5+10 ;

using namespace std ;

struct SparseSeg
{

	vector< int > _sum, e , d ;
	
	int create()
	{
		_sum.push_back(0) ;
		e.push_back(0) ;
		d.push_back(0) ;
		return sz(e)-1 ;
	}

	int m(int l, int r) { return (l+r)>>1 ; }
	
	void upd(int pos, int l, int r, int idx )
	{
		
		_sum[pos]++ ;


		if( l == r ) return ;

		int aux ;

		if( idx <= m(l,r) )
		{
			if(e[pos] == 0 ) { aux = create() ; e[pos] = aux ; }
			upd(e[pos] , l ,m(l,r), idx ) ;
		}
		else 
		{
			if(d[pos] == 0 ) { aux = create() ; d[pos] = aux ; }
			upd(d[pos] , m(l,r)+1, r, idx ) ;
		}

	}

	int qry(int pos, int l, int r, int bValue )
	{
		if( r < bValue || !pos ) return 0 ;
		if( l >= bValue ) return _sum[pos] ;

		int al = qry(e[pos] , l , m(l,r) , bValue ) ;
		int ar = qry(d[pos] , m(l,r) + 1 , r , bValue ) ;

		return al + ar ;
	}

} ;

int N , Q , Key ;
map<int,int> coordinateCompression ;
SparseSeg bit[MAXN] ;

void upd(int aValue, int bValue )
{
	for(; aValue <= Key ; aValue += aValue & -aValue)
		bit[aValue].upd(1,1,Key, bValue ) ;
}

int qry(int aValue, int bValue )
{
	int tot = 0 ;

	for(; aValue > 0  ; aValue -= aValue & -aValue )
		tot += bit[aValue].qry(1,1,Key, bValue ) ;

	return tot ;	
}

int main()
{
	scanf("%d %d", &N, &Q ) ;

	vector< pair<int,int> > sweep ;
	vector< pair<int,int> > student(N+1) ;
	vector< pair<int,int> > queries(Q+1) ;
   vector<int> ansQueries(Q+1,0) ;

	for(int i = 1 ; i <= N ; i++ )
    {
        scanf("%d %d", &student[i].first, &student[i].second  ) ;

        coordinateCompression[ student[i].first ] = 0 ;
        coordinateCompression[ student[i].second ] = 0 ;
        sweep.push_back( make_pair(student[i].first + student[i].second , i) ) ;
    }
	for(int i = 1 , C ; i <= Q ; i++ )
	{
		scanf("%d %d %d", &queries[i].first ,&queries[i].second, &C ) ;

		coordinateCompression[ queries[i].first ] = 0 ;
		coordinateCompression[ queries[i].second ] = 0 ;
		sweep.push_back( make_pair(C, -i ) );
	}


	for(auto &e : coordinateCompression ) e.second = ++Key ;

	sort(all(sweep) ) ;
	for(int i = 1 ; i <= Key ; i++ ) bit[i].create() , bit[i].create() ;

	for(int i = sz(sweep)-1 ; i >= 0 ; i-- )
	{

      auto e = sweep[i] ;

		if( e.second > 0 )
		{
		    int A = student[ e.second ].first ;
		    int B = student[ e.second ].second ;

		    A = coordinateCompression[A] ;
		    B = coordinateCompression[B] ;

		    upd( A , B ) ;
		}
		else
      {
          int idQuery = -e.second ;
          int A = queries[idQuery].first ;
          int B = queries[idQuery].second ;

          A = coordinateCompression[A] ;
          B = coordinateCompression[B] ;

          ansQueries[idQuery] = qry(Key, B) - qry(A-1, B) ;

      } 

	} 

	for(int i = 1 ; i <= Q ; i++ ) printf("%d\n" , ansQueries[i]) ;

}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d %d", &N, &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         scanf("%d %d", &student[i].first, &student[i].second  ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf("%d %d %d", &queries[i].first ,&queries[i].second, &C ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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