// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// Nhan qua khong no chung ta thu gi //
// Vay nen dung oan han //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// //
// _oo0oo_ //
// o8888888o //
// 88" . "88 //
// (| -_- |) //
// 0\ = /0 //
// ___/`---'\___ //
// .' \\| |// '. //
// / \\||| : |||// \ //
// / _||||| -:- |||||- \ //
// | | \\\ - /// | | //
// | \_| ''\---/'' |_/ | //
// \ .-\__ '-' ___/-. / //
// ___'. .' /--.--\ `. .'___ //
// ."" '< `.___\_<|>_/___.' >' "". //
// | | : `- \`.;`\ _ /`;.`/ - ` : | | //
// \ \ `_. \_ __\ /__ _/ .-` / / //
// =====`-.____`.___ \_____/___.-`___.-'===== //
// `=---=' //
// //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
// Duc Phat noi day phu ho Code con chay khong Bug //
// Nam mo a di da phat //
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //
#include<bits/stdc++.h>
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "Orz_chUoNgnn"
#endif
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 1e6;
int tc, tt = 1;
struct student {
ll a, b, c;
ll in, q;
} a[N + 5];
#define vi vector<student>
int n, q;
vector<int> f;
map<int, int> pos;
ll ans[N + 5];
struct fenwick_tree {
ll ft[N + 5];
void update(int pos, int val) {
int idx = pos;
while(idx <= N) {
ft[idx] += val;
idx += (idx & (-idx));
}
}
ll get(int pos) {
int idx = pos;
ll ans = 0;
while(idx > 0) {
ans += ft[idx];
idx -= (idx & (-idx));
}
return ans;
}
} ft;
vi cdq(int l, int r) {
vi f;
vector<int> record;
if(l == r) {
f.pb(a[l]);
return f;
}
int mid = (l + r)/2;
vi a = cdq(l, mid);
vi b = cdq(mid + 1, r);
int i = 0, j = 0, cnt = 0;
while(i < (int)a.size() && j < (int)b.size()) {
if(a[i].b >= b[j].b) {
f.pb(a[i]);
if(a[i].in) {
cnt++;
ft.update(pos[a[i].c], 1);
record.pb(pos[a[i].c]);
}
i++;
}
else {
if(!b[j].in)
ans[b[j].q] += cnt - ft.get(pos[b[j].c]);
f.pb(b[j]);
j++;
}
}
while(i < (int)a.size()) {f.pb(a[i]); i++;}
while(j < (int)b.size()) {
if(!b[j].in)
ans[b[j].q] += cnt - ft.get(pos[b[j].c]);
f.pb(b[j]);
j++;
}
for(auto x: record) ft.update(x, -1);
return f;
}
void solve() {
cin>>n>>q;
for(int i=1; i<=n + q; i++) {
a[i].a = a[i].b = a[i].c = a[i].in = 0;
}
for(int i=1; i<=n; i++) {
cin>>a[i].a>>a[i].b;
a[i].c = a[i].a + a[i].b;
a[i].in = 1;
}
for(int i=n + 1; i<=n + q; i++) {
cin>>a[i].a>>a[i].b>>a[i].c;
a[i].a--;
a[i].b--;
a[i].c--;
a[i].q = i - n;
}
n += q;
for(int i=1; i<=n; i++) {
f.pb(a[i].a);
f.pb(a[i].b);
f.pb(a[i].c);
}
sort(f.begin(), f.end());
f.erase(unique(f.begin(), f.end()), f.end());
for(int i=0; i<(int)f.size(); i++) pos[f[i]] = i + 1;
sort(a + 1, a + 1 + n, [](student x, student y){
if(x.a != y.a) return x.a > y.a;
if(x.in == 1) return true;
if(x.in == 0 && y.in == 1) return false;
if(x.b != y.b) return x.b > y.b;
return x.c > y.c;
});
cdq(1, n);
for(int i=1; i<=q; i++)
cout<<ans[i]<<'\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen(".INP", "r", stdin);
// freopen(".OUT", "w", stdout);
for(int tc=1; tc<=tt; tc++) solve();
cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
474 ms |
52920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
474 ms |
52920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
