oj.uz

Submission #333063

# Submission time Handle Problem Language Result Execution time Memory
333063 2020-12-04T11:51:52 Z CaroLinda Examination (JOI19_examination) C++14
2 / 100
 3000 ms 272444 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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 ;
using namespace __gnu_pbds ;

#define ordered_set tree< pair<int,int> , null_type, less< pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update>

struct Seg
{

	ordered_set vec[MAXN*4] ;

	int m(int l, int r) { return (l+r)>>1 ; }

	void upd(int pos, int l, int r, int aValue, int bValue , int idValue )
	{
	    vec[pos].insert( make_pair(bValue, idValue) ) ;

	    if(l == r) return ;

	    if( aValue <= m(l,r) ) upd(pos<<1 , l, m(l,r) , aValue, bValue , idValue ) ;
	    else upd(pos<<1|1 , m(l,r)+1, r, aValue, bValue, idValue ) ;

	}

	int qry(int pos, int l, int r, int aValue, int bValue)
	{
	    if(r < aValue ) return 0 ;
	    if( l >= aValue ) return sz(vec[pos]) - vec[pos].order_of_key(make_pair(bValue, 0)) ;

	    int al = qry(pos<<1 , l , m(l,r) , aValue , bValue ) ;
	    int ar = qry(pos<<1|1 , m(l,r)+1, r, aValue, bValue ) ;

	    return al + ar ;

	}

} seg ;

int N , Q ;
map<int,int> coordinateCompression ;

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

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

	sort(all(sweep) ) ;

	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] ;

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

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

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

        }

	}

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

}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d %d", &N, &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%d %d", &student[i].first, &student[i].second  ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   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 140 ms 150636 KB Output is correct
2 Correct 142 ms 150636 KB Output is correct
3 Correct 144 ms 150636 KB Output is correct
4 Correct 141 ms 150764 KB Output is correct
5 Correct 142 ms 150636 KB Output is correct
6 Correct 140 ms 150636 KB Output is correct
7 Correct 170 ms 154348 KB Output is correct
8 Correct 168 ms 154220 KB Output is correct
9 Correct 170 ms 154220 KB Output is correct
10 Correct 159 ms 153708 KB Output is correct
11 Correct 165 ms 153708 KB Output is correct
12 Correct 149 ms 151660 KB Output is correct
13 Correct 168 ms 154220 KB Output is correct
14 Correct 182 ms 154240 KB Output is correct
15 Correct 164 ms 154368 KB Output is correct
16 Correct 169 ms 153836 KB Output is correct
17 Correct 158 ms 153708 KB Output is correct
18 Correct 147 ms 151404 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2972 ms 272444 KB Output is correct
2 Execution timed out 3102 ms 272432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2972 ms 272444 KB Output is correct
2 Execution timed out 3102 ms 272432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 150636 KB Output is correct
2 Correct 142 ms 150636 KB Output is correct
3 Correct 144 ms 150636 KB Output is correct
4 Correct 141 ms 150764 KB Output is correct
5 Correct 142 ms 150636 KB Output is correct
6 Correct 140 ms 150636 KB Output is correct
7 Correct 170 ms 154348 KB Output is correct
8 Correct 168 ms 154220 KB Output is correct
9 Correct 170 ms 154220 KB Output is correct
10 Correct 159 ms 153708 KB Output is correct
11 Correct 165 ms 153708 KB Output is correct
12 Correct 149 ms 151660 KB Output is correct
13 Correct 168 ms 154220 KB Output is correct
14 Correct 182 ms 154240 KB Output is correct
15 Correct 164 ms 154368 KB Output is correct
16 Correct 169 ms 153836 KB Output is correct
17 Correct 158 ms 153708 KB Output is correct
18 Correct 147 ms 151404 KB Output is correct
19 Correct 2972 ms 272444 KB Output is correct
20 Execution timed out 3102 ms 272432 KB Time limit exceeded
21 Halted 0 ms 0 KB -