#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 tree[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 )
{
tree[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(tree[pos]) - tree[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:20:14: error: declaration of '__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Seg::tree [1600040]' changes meaning of 'tree' [-fpermissive]
20 | ordered_set tree[MAXN*4] ;
| ^~~~
In file included from examination.cpp:2:
/usr/include/c++/9/ext/pb_ds/assoc_container.hpp:635:9: note: 'tree' declared here as 'class __gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>'
635 | class tree : public PB_DS_TREE_BASE
| ^~~~
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 ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
