oj.uz

Submission #333078

# Submission time Handle Problem Language Result Execution time Memory
333078 2020-12-04T12:16:41 Z CaroLinda Examination (JOI19_examination) C++14
100 / 100
 2945 ms 297764 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Correct 19 ms 28524 KB Output is correct
5 Correct 19 ms 28524 KB Output is correct
6 Correct 19 ms 28524 KB Output is correct
7 Correct 50 ms 33772 KB Output is correct
8 Correct 48 ms 33772 KB Output is correct
9 Correct 48 ms 33772 KB Output is correct
10 Correct 35 ms 30572 KB Output is correct
11 Correct 35 ms 31596 KB Output is correct
12 Correct 22 ms 28652 KB Output is correct
13 Correct 50 ms 33832 KB Output is correct
14 Correct 50 ms 33772 KB Output is correct
15 Correct 50 ms 33772 KB Output is correct
16 Correct 35 ms 31724 KB Output is correct
17 Correct 32 ms 30316 KB Output is correct
18 Correct 22 ms 28652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2214 ms 183276 KB Output is correct
2 Correct 2122 ms 183008 KB Output is correct
3 Correct 2118 ms 185180 KB Output is correct
4 Correct 804 ms 74076 KB Output is correct
5 Correct 825 ms 89948 KB Output is correct
6 Correct 121 ms 33756 KB Output is correct
7 Correct 1885 ms 183784 KB Output is correct
8 Correct 1965 ms 183904 KB Output is correct
9 Correct 1595 ms 178816 KB Output is correct
10 Correct 792 ms 89692 KB Output is correct
11 Correct 612 ms 71900 KB Output is correct
12 Correct 94 ms 33504 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2214 ms 183276 KB Output is correct
2 Correct 2122 ms 183008 KB Output is correct
3 Correct 2118 ms 185180 KB Output is correct
4 Correct 804 ms 74076 KB Output is correct
5 Correct 825 ms 89948 KB Output is correct
6 Correct 121 ms 33756 KB Output is correct
7 Correct 1885 ms 183784 KB Output is correct
8 Correct 1965 ms 183904 KB Output is correct
9 Correct 1595 ms 178816 KB Output is correct
10 Correct 792 ms 89692 KB Output is correct
11 Correct 612 ms 71900 KB Output is correct
12 Correct 94 ms 33504 KB Output is correct
13 Correct 1953 ms 185832 KB Output is correct
14 Correct 2199 ms 185436 KB Output is correct
15 Correct 2166 ms 184808 KB Output is correct
16 Correct 754 ms 74492 KB Output is correct
17 Correct 836 ms 91600 KB Output is correct
18 Correct 131 ms 33884 KB Output is correct
19 Correct 1933 ms 185312 KB Output is correct
20 Correct 2045 ms 185404 KB Output is correct
21 Correct 1680 ms 182840 KB Output is correct
22 Correct 779 ms 89824 KB Output is correct
23 Correct 608 ms 72028 KB Output is correct
24 Correct 92 ms 33376 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Correct 19 ms 28524 KB Output is correct
5 Correct 19 ms 28524 KB Output is correct
6 Correct 19 ms 28524 KB Output is correct
7 Correct 50 ms 33772 KB Output is correct
8 Correct 48 ms 33772 KB Output is correct
9 Correct 48 ms 33772 KB Output is correct
10 Correct 35 ms 30572 KB Output is correct
11 Correct 35 ms 31596 KB Output is correct
12 Correct 22 ms 28652 KB Output is correct
13 Correct 50 ms 33832 KB Output is correct
14 Correct 50 ms 33772 KB Output is correct
15 Correct 50 ms 33772 KB Output is correct
16 Correct 35 ms 31724 KB Output is correct
17 Correct 32 ms 30316 KB Output is correct
18 Correct 22 ms 28652 KB Output is correct
19 Correct 2214 ms 183276 KB Output is correct
20 Correct 2122 ms 183008 KB Output is correct
21 Correct 2118 ms 185180 KB Output is correct
22 Correct 804 ms 74076 KB Output is correct
23 Correct 825 ms 89948 KB Output is correct
24 Correct 121 ms 33756 KB Output is correct
25 Correct 1885 ms 183784 KB Output is correct
26 Correct 1965 ms 183904 KB Output is correct
27 Correct 1595 ms 178816 KB Output is correct
28 Correct 792 ms 89692 KB Output is correct
29 Correct 612 ms 71900 KB Output is correct
30 Correct 94 ms 33504 KB Output is correct
31 Correct 1953 ms 185832 KB Output is correct
32 Correct 2199 ms 185436 KB Output is correct
33 Correct 2166 ms 184808 KB Output is correct
34 Correct 754 ms 74492 KB Output is correct
35 Correct 836 ms 91600 KB Output is correct
36 Correct 131 ms 33884 KB Output is correct
37 Correct 1933 ms 185312 KB Output is correct
38 Correct 2045 ms 185404 KB Output is correct
39 Correct 1680 ms 182840 KB Output is correct
40 Correct 779 ms 89824 KB Output is correct
41 Correct 608 ms 72028 KB Output is correct
42 Correct 92 ms 33376 KB Output is correct
43 Correct 2731 ms 297764 KB Output is correct
44 Correct 2713 ms 297276 KB Output is correct
45 Correct 2945 ms 297404 KB Output is correct
46 Correct 1091 ms 116944 KB Output is correct
47 Correct 1107 ms 149536 KB Output is correct
48 Correct 130 ms 33776 KB Output is correct
49 Correct 2655 ms 294108 KB Output is correct
50 Correct 2456 ms 293724 KB Output is correct
51 Correct 2250 ms 275768 KB Output is correct
52 Correct 1112 ms 151368 KB Output is correct
53 Correct 854 ms 113588 KB Output is correct