Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Problem: segtree
- * Correct solution (must be OK).
- * Author: stgatilov
- * Solution: Build tree with sets of segments in it
- * Time: avg O(N log N) with O(N) memory
- */
- //#pragma comment(linker, "/STACK:20000000")
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <algorithm>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstring>
- #include <cassert>
- #include <cstdlib>
- #include <ctime>
- #include <cstdint>
- #include <unordered_set>
- #include <cinttypes>
- #include <array>
- #include <memory>
- using namespace std;
- typedef long long int64;
- #ifdef HOME
- #define E(c) cerr<<#c
- #define Eo(x) cerr<<#x<<" = "<<(x)<<endl
- #define Ef(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define E(c) ((void)0)
- #define Eo(x) ((void)0)
- #define Ef(...) ((void)0)
- #endif
- #define SHIFT
- const int64 MULT = 1000000;
- const int BLOCK = 32;
- typedef vector<int> idxList;
- struct Segment {
- int64 l, r;
- };
- int n;
- int64 m;
- vector<Segment> arr;
- int h;
- vector<vector<idxList>> tree;
- int statCells, statChecks, statFound;
- int64 Width(int lvl) {
- return ((BLOCK * MULT) << lvl);
- }
- int GetLevel(int64 len) {
- int lvl = 0;
- while (Width(lvl) < len)
- lvl++;
- return lvl;
- }
- int AddSegment(const Segment &seg) {
- int lvl = GetLevel(seg.r - seg.l);
- int64 wid = Width(lvl);
- int li = seg.l / wid;
- int ri = (seg.r + wid-1) / wid;
- int id = arr.size();
- arr.push_back(seg);
- for (int i = li; i < ri; i++)
- tree[lvl][i].push_back(id);
- return id;
- }
- void FindSegments(int64 where, int &sum, int &cnt) {
- sum = cnt = 0;
- for (int lvl = 0; lvl <= h; lvl++) {
- const auto &row = tree[lvl];
- int64 wid = Width(lvl);
- int cell = where / wid;
- statCells++;
- for (int id : row[cell]) {
- statChecks++;
- if (arr[id].l <= where && where < arr[id].r) {
- sum += id;
- cnt++;
- }
- }
- }
- statFound += cnt;
- }
- void Init(int n) {
- ::n = n;
- ::m = n * MULT;
- ::h = 0;
- while (Width(h) < m + 16)
- h++;
- arr.reserve(n);
- tree.resize(h + 1);
- for (int lvl = 0; lvl <= h; lvl++) {
- int64 wid = Width(lvl);
- int k = (m + wid-1) / wid;
- tree[lvl].resize(k);
- }
- }
- int main(int argc, char **argv) {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- scanf("%d", &n);
- Init(n);
- int64 shift = 0;
- for (int i = 0; i < 2*n; i++) {
- int t;
- scanf("%d", &t);
- if (t == 0) {
- double rCtr, rRad;
- scanf("%lf%lf", &rCtr, &rRad);
- int64 ctr = int64(MULT * rCtr + 0.5);
- int64 rad = int64(MULT * rRad + 0.5);
- ctr = (ctr + shift) % m;
- Segment seg = {max(ctr - rad, 0LL), min(ctr + rad + 1, m)};
- AddSegment(seg);
- }
- else {
- double rWhere;
- scanf("%lf", &rWhere);
- int64 where = int64(MULT * rWhere + 0.5);
- where = (where + shift) % m;
- int sum, cnt;
- FindSegments(where, sum, cnt);
- #ifdef SHIFT
- shift = (shift + sum * MULT) % m;
- #else
- printf("[%d] ", sum);
- #endif
- printf("%d\n", cnt);
- }
- }
- Ef("cells: %d; found: %d/%d\n", statCells, statFound, statChecks);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement