#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST;
#define int long long
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
OST bit[MAXN]; // 2D bit in binary matrices
void insert(int x, int y) {
for(;x<MAXN;x+=x&-x) bit[x].insert({y, x});
}
void erase(int x, int y) {
for(;x<MAXN;x+=x&-x) bit[x].erase({y, x});
}
int query(int x, int y) {
int sum = 0;
for(;x;x-=x&-x) sum += bit[x].order_of_key({y+1, 0});
return sum;
}
struct event {
int type; // type = 0: "insert", type > 0: "query"
int a, b, c;
};
bool cmp(event x, event y) {
if(x.c == y.c) return x.type < y.type;
return x.c > y.c;
}
void solve(int tc) {
int n, q;
cin >> n >> q;
event e[n + q + 1];
for(int i=1; i<=n; i++) {
e[i].type = 0;
cin >> e[i].a >> e[i].b;
e[i].c = e[i].a + e[i].b;
}
for(int i=1; i<=q; i++) {
e[n+i].type = i;
cin >> e[n+i].a >> e[n+i].b >> e[n+i].c;
}
sort(e + 1, e+n+q + 1, cmp);
int ans[q+1];
for(int i=1; i<=n+q; i++) {
if(e[i].type == 0) {
insert(e[i].a + 1, e[i].b + 1);
}
else {
ans[e[i].type] = query(200001, 200001) - query(200001, e[i].b)
- query(e[i].a, 200001) + query(e[i].a, e[i].b);
}
}
for(int i=1; i<=q; i++) {
cout << ans[i] << "\n";
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
19052 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
19020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1472 ms |
83844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1472 ms |
83844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
19052 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
19020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
