niyaznigmatullin

Untitled

Jul 7th, 2013
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.65 KB | None | 0 0
  1. import java.io.IOException;
  2. import java.io.InputStreamReader;
  3. import java.io.BufferedReader;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.util.Random;
  7. import java.io.Writer;
  8. import java.util.StringTokenizer;
  9. import java.io.InputStream;
  10.  
  11. /**
  12. * Built using CHelper plug-in
  13. * Actual solution is at the top
  14. * @author niyaznigmatul
  15. */
  16. public class Main {
  17.    public static void main(String[] args) {
  18.        InputStream inputStream = System.in;
  19.        OutputStream outputStream = System.out;
  20.        FastScanner in = new FastScanner(inputStream);
  21.        FastPrinter out = new FastPrinter(outputStream);
  22.        Task2310 solver = new Task2310();
  23.        solver.solve(1, in, out);
  24.        out.close();
  25.    }
  26. }
  27.  
  28. class Task2310 {
  29.  
  30.    static final int MAXY = 1000000000;
  31.  
  32.    static final Random rand = new Random(123123L);
  33.  
  34.    static class Node {
  35.        Node left;
  36.        Node right;
  37.        long sum;
  38.        int x;
  39.        int y;
  40.  
  41.        Node(int x, int y) {
  42.            this.x = x;
  43.            this.y = y;
  44.            sum = x;
  45.        }
  46.  
  47.        void collect() {
  48.            sum = x;
  49.            if (left != null) {
  50.                sum += left.sum;
  51.            }
  52.            if (right != null) {
  53.                sum += right.sum;
  54.            }
  55.        }
  56.    }
  57.  
  58.    static Node merge(Node first, Node second) {
  59.        if (first == null) {
  60.            return second;
  61.        }
  62.        if (second == null) {
  63.            return first;
  64.        }
  65.        Node ret;
  66.        if (first.y > second.y) {
  67.            first.right = merge(first.right, second);
  68.            ret = first;
  69.        } else {
  70.            second.left = merge(first, second.left);
  71.            ret = second;
  72.        }
  73.        ret.collect();
  74.        return ret;
  75.    }
  76.  
  77.    static Node[] split(Node v, int x) {
  78.        if (v == null) {
  79.            return new Node[2];
  80.        }
  81.        Node[] ret;
  82.        if (v.x <= x) {
  83.            ret = split(v.right, x);
  84.            v.right = ret[0];
  85.            ret[0] = v;
  86.        } else {
  87.            ret = split(v.left, x);
  88.            v.left = ret[1];
  89.            ret[1] = v;
  90.        }
  91.        v.collect();
  92.        return ret;
  93.    }
  94.  
  95.    static Node add(Node v, int x, int y) {
  96.        if (v == null) {
  97.            return new Node(x, y);
  98.        }
  99.        if (v.y < y) {
  100.            Node[] t = split(v, x);
  101.            Node ret = new Node(x, y);
  102.            ret.left = t[0];
  103.            ret.right = t[1];
  104.            ret.collect();
  105.            return ret;
  106.        }
  107.        if (v.x < x) {
  108.            v.right = add(v.right, x, y);
  109.        } else {
  110.            v.left = add(v.left, x, y);
  111.        }
  112.        v.collect();
  113.        return v;
  114.    }
  115.  
  116.    static boolean contains(Node v, int x) {
  117.        if (v == null) {
  118.            return false;
  119.        }
  120.        if (v.x == x) {
  121.            return true;
  122.        } else if (v.x < x) {
  123.            return contains(v.right, x);
  124.        } else {
  125.            return contains(v.left, x);
  126.        }
  127.    }
  128.  
  129.    static Node root;
  130.  
  131.    static long getSum(int l, int r) {
  132.        if (l > r) {
  133.            return 0;
  134.        }
  135.        Node[] t1 = split(root, r);
  136.        Node[] t2 = split(t1[0], l - 1);
  137.        long ret = t2[1] == null ? 0 : t2[1].sum;
  138.        root = merge(merge(t2[0], t2[1]), t1[1]);
  139.        return ret;
  140.    }
  141.  
  142.    public void solve(int testNumber, FastScanner in, FastPrinter out) {
  143.        int n = in.nextInt();
  144.        long y = 0;
  145.        for (int i = 0; i < n; i++) {
  146.            if (in.next().equals("+")) {
  147.                int x = in.nextInt();
  148.                x = (int) ((x + y) % MAXY);
  149.                if (!contains(root, x)) {
  150.                    root = add(root, x, rand.nextInt());
  151.                }
  152.                y = 0;
  153.            } else {
  154.                int l = in.nextInt();
  155.                int r = in.nextInt();
  156.                y = getSum(l, r);
  157.                out.println(y);
  158.            }
  159.        }
  160.    }
  161. }
  162.  
  163. class FastScanner {
  164.    BufferedReader br;
  165.    StringTokenizer st;
  166.    IOException happened;
  167.  
  168.    public FastScanner(InputStream is) {
  169.        br = new BufferedReader(new InputStreamReader(is));
  170.    }
  171.  
  172.    public String next() {
  173.        while (st == null || !st.hasMoreTokens()) {
  174.            try {
  175.                String line = br.readLine();
  176.                st = new StringTokenizer(line);
  177.            } catch (IOException e) {
  178.                happened = e;
  179.                return null;
  180.            }
  181.        }
  182.        return st.nextToken();
  183.    }
  184.  
  185.    public int nextInt() {
  186.        return Integer.parseInt(next());
  187.    }
  188.  
  189.    }
  190.  
  191. class FastPrinter extends PrintWriter {
  192.  
  193.    public FastPrinter(OutputStream out) {
  194.        super(out);
  195.    }
  196.  
  197.    public FastPrinter(Writer out) {
  198.        super(out);
  199.    }
  200.  
  201.  
  202. }
Advertisement
Add Comment
Please, Sign In to add comment