Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define fi first
- #define se second
- #define amen exit(0)
- #define endl "\n"
- using namespace std;
- using namespace __gnu_pbds;
- typedef int ll;
- typedef pair <ll, ll> pii;
- typedef long double ld;
- template <class type1>
- using super_set = tree <type1, null_type, less <type1>, rb_tree_tag, tree_order_statistics_node_update>;
- template <class type1, class type2>
- using super_map = tree <type1, type2, less <type1>, rb_tree_tag, tree_order_statistics_node_update>;
- #define tree nado_ubrat_tree_potomu_chto_tree_est_v_biblioteke_s_super_setom
- const ll D = 200007;
- const ll Inf = 1000000107;
- const ll block = 3000;
- vector <pii> a, additive;
- vector <ll> tree[4*D];
- ll n, m;
- void combine(ll v)
- {
- tree[v].resize(tree[v*2 + 1].size() + tree[v*2 + 2].size());
- merge(tree[v*2 + 1].begin(), tree[v*2 + 1].end(),
- tree[v*2 + 2].begin(), tree[v*2 + 2].end(),
- tree[v].begin());
- }
- void build_tree(ll v, ll sl, ll sr)
- {
- if (sl == sr)
- {
- tree[v].push_back(a[sl].se);
- return;
- }
- ll mid = (sl + sr) / 2;
- build_tree(v*2 + 1, sl, mid);
- build_tree(v*2 + 2, mid + 1, sr);
- combine(v);
- }
- ll get(ll v, ll sl, ll sr, ll xl, ll yl, ll xr, ll yr)
- {
- if (xl > sr || xr < sl)
- return 0;
- if (xl <= sl && sr <= xr)
- return upper_bound(tree[v].begin(), tree[v].end(), yr) -
- lower_bound(tree[v].begin(), tree[v].end(), yl);
- ll mid = (sl + sr) / 2;
- return get(v*2 + 1, sl, mid, xl, yl, xr, yr) +
- get(v*2 + 2, mid + 1, sr, xl, yl, xr, yr);
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- ll x1, y1, x2, y2;
- cin >> n;
- for (ll i = 1; i <= n; i++)
- cin >> x1 >> y1, a.push_back({x1, y1});
- sort(a.begin(), a.end());
- build_tree(0, 0, n - 1);
- char id;
- ll res = 0;
- cin >> m;
- for (ll i = 1; i <= m; i++)
- {
- cin >> id >> x1 >> y1;
- if (id == '?')
- {
- cin >> x2 >> y2;
- res = 0;
- for (pii val : additive)
- if (x1 <= val.fi && val.fi <= x2 && y1 <= val.se && val.se <= y2)
- res++;
- x1 = lower_bound(a.begin(), a.end(), (pii) {x1, 0}) - a.begin();
- x2 = lower_bound(a.begin(), a.end(), (pii) {x2 + 1, 0}) - a.begin() - 1;
- res += get(0, 0, a.size() - 1, x1, y1, x2, y2);
- cout << res << endl;
- }
- else
- {
- additive.push_back({x1 + res % 100, y1 + res % 101});
- if (additive.size() >= block)
- {
- for (pii val : additive)
- a.push_back(val);
- additive.clear();
- sort(a.begin(), a.end());
- build_tree(0, 0, a.size() - 1);
- }
- }
- }
- amen;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement