This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
#define int long long
const long long inf = 1e18+1;
const int mod = 1e9+7;
const int MAXN = 3e6+100;
struct BIT {
int b[MAXN], n;
void init(int _n) {
n = _n;
for(int i = 0 ; i <= n ; ++i) b[i] = 0;
}
inline int lowbit(int x) { return x & (-x); }
void update(int x, int v) {
for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
}
int query(int x) {
int ans = 0;
for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
return ans;
}
} bit;
struct Pt{
int x , y , z , i , t;
};
struct cmp{
bool operator() (Pt a , Pt b){
return (a.x == b.x ? (a.y == b.y ? a.z > b.z : a.y > b.y) : a.x > b.x);
}
};
Pt a[MAXN];
int ans[MAXN];
void cdq(int l , int r){
if(l == r) return ;
int mid = l + r >> 1;
cdq(l , mid) ; cdq(mid+1 , r);
int i = l, j = mid+1 ,sum = 0;
vector<int> record;
vector<Pt> tmp;
while(i <= mid && j <= r){
if(a[i].y >= a[j].y) {
if(a[i].t == 0) bit.update(a[i].z , 1) , sum ++ , record.push_back(a[i].z);
tmp.push_back(a[i++]);
}
else{
ans[a[j].i] += sum - bit.query(a[j].z);
tmp.push_back(a[j++]);
}
}
while(i <= mid) tmp.push_back(a[i++]);
while(j <= r) ans[a[j].i] += sum - bit.query(a[j].z), tmp.push_back(a[j++]);
for(int i = l ; i <= r ; i++) a[i] = tmp[i-l];
for(auto i : record) bit.update(i , -1);
vector<int> ().swap(record);
vector<Pt> ().swap(tmp);
}
map<int , int> mp;
map<Pt , int , cmp> cnt;
int32_t main(){
//freopen("KNIGHTGAME.inp", "r", stdin);
//freopen("KNIGHTGAME.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n , q; cin >> n >> q;
vector<int> comp;
for(int i = 1 ; i <= n ; i++) cin >> a[i].x >> a[i].y, a[i].i = i , a[i].z = a[i].x + a[i].y, a[i].t = 0 , cnt[{a[i].x , a[i].y , a[i].z , 1 , 0}]++, comp.push_back(a[i].z);
for(int j = 1 ; j <= q ; j ++){
int x , y , z; cin>> x >> y >> z;
Pt t = {x , y , z , 1 , 0};
ans[n + j];
a[n + j] = {x , y , z , n + j , 1};
comp.push_back(z);
}
sort(all(comp));
comp.erase(unique(comp.begin() , comp.end()) , comp.end());
for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
for(int i = 1 ; i <= n + q ; i++) a[i].z = mp[a[i].z];
sort(a+1, a+n+q+1, [&](auto a, auto b) {
return (a.x == b.x ? (a.y == b.y ? a.z > b.z : a.y > b.y) : a.x > b.x);
});
bit.init(n + q);
cdq(1 , n + q);
for(int i = 1 ; i <= q ; i++){
cout << ans[n + i] << "\n";
}
return 0;
}
Compilation message (stderr)
examination.cpp: In function 'void cdq(long long int, long long int)':
examination.cpp:44:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = l + r >> 1;
| ~~^~~
examination.cpp: In function 'int32_t main()':
examination.cpp:79:12: warning: statement has no effect [-Wunused-value]
79 | ans[n + j];
| ~~~~~~~~~^
examination.cpp:78:6: warning: unused variable 't' [-Wunused-variable]
78 | Pt t = {x , y , z , 1 , 0};
| ^
examination.cpp:85:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0 ; i < comp.size() ;i++) mp[comp[i]] = i+1;
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |