/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed
/* GNU G++17 7.3.0: No long long for faster code
GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
#include <bits/stdc++.h>
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6
using namespace std;
struct Point{
int x, y, z, id, ans;
bool operator< (Point const& o) {
if (x != o.x) return x > o.x;
if (y != o.y) return y > o.y;
return z > o.z;
}
};
const int k = 6e5;
int n, q;
map<int, int> mp;
int res[100005], fentree[600005];
vector<Point> v, s;
void update(int i, int val) {
for (; i <= k; i += i & -i) fentree[i] += val;
}
int get(int i) {
int res = 0;
for (; i; i -= i & -i) res += fentree[i];
return res;
}
void cdq(int l, int r, vector<Point>& v) {
if (l == r) return;
int m = (l + r)/2;
cdq(l, m, v); cdq(m + 1, r, v);
// cout << l << " " << r << "\n";
// for1(i,l,r) cout << v[i].x << " " << v[i].y << " " << v[i].z << "\n";
vector<Point> st;
vector<int> roll;
int a = l, b = m + 1, sum = 0;
while (a <= m && b <= r) {
if (v[a].y > v[b].y) {
sum++;
update(v[a].z, 1);
roll.push_back(v[a].z);
st.push_back(v[a++]);
}
else {
v[b].ans += sum - get(v[b].z);
// cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
st.push_back(v[b++]);
}
}
while (a <= m) st.push_back(v[a++]);
while (b <= r) {
v[b].ans += sum - get(v[b].z);
// cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
st.push_back(v[b++]);
}
// cout << "\n";
for1(i,l,r) v[i] = st[i - l];
for (auto x : roll) update(x, -1);
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("cf.inp", "r", stdin);
// freopen("cf.out", "w", stdout);
cin >> n >> q;
for1(i,1,n) {
int a, b;
cin >> a >> b;
v.push_back({a, b, a + b, 0, 0});
mp[a] = 0;
mp[b] = 0;
mp[a + b] = 0;
}
for1(i,1,q) {
int x, y, z;
cin >> x >> y >> z;
x--; y--; z--;
v.push_back({x, y, z, i, 0});
s.push_back({x, y, z, i, 0});
mp[x] = 0;
mp[y] = 0;
mp[z] = 0;
}
int cur = 0;
for (auto &p : mp) p.second = ++cur;
for (auto &p : v) p.x = mp[p.x], p.y = mp[p.y], p.z = mp[p.z];
for (auto &p : s) p.x = mp[p.x], p.y = mp[p.y], p.z = mp[p.z];
sort(v.begin(), v.end());
sort(s.begin(), s.end());
cdq(0, n + q - 1, v);
cdq(0, q - 1, s);
// for (auto p : v) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
// cout << "\n";
// for (auto p : s) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
// cout << "\n";
for (auto p : v) if (p.id) res[p.id] += p.ans;
for (auto p : s) res[p.id] -= p.ans;
for1(i,1,q) cout << res[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
967 ms |
41744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
967 ms |
41744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
