Advertisement
Guest User

Untitled

a guest
May 20th, 2011
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.01 KB | None | 0 0
  1.     import java.io.*;
  2.     import java.util.*;
  3.     import java.math.*;
  4.  
  5.     public class D implements Runnable {
  6.             private final boolean useStandardIO = true;
  7.             private final String inFile = ".in";
  8.             private final String outFile = ".out";
  9.  
  10.             class Command {
  11.                     String name;
  12.                     int x;
  13.             }
  14.  
  15.             private void solve() throws IOException {
  16.                     int n = nextInt();
  17.                     List<Command> cmds = new ArrayList<Command>();
  18.                     List<Integer> all = new ArrayList<Integer>();
  19.                     for (int i = 0; i < n; ++i) {
  20.                             String cmd = nextToken();
  21.                             Command c = new Command();
  22.                             if (cmd.equals("sum")) {
  23.                             } else {
  24.                                     int x = nextInt();
  25.                                     c.x = x;
  26.                                     all.add(x);
  27.                             }
  28.                             c.name = cmd;
  29.                             cmds.add(c);
  30.                     }
  31.                     Collections.sort(all);
  32.                     Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
  33.                     int z = 0;
  34.                     for (int i = 0; i < all.size(); ++i)
  35.                             if (i == 0 || all.get(i) != all.get(i - 1)) {
  36.                                     hm.put(all.get(i), z++);
  37.                             }
  38.                     Node root = createTree(0, hm.size());
  39.                     for (Command c : cmds) {
  40.                             if (c.name.equals("sum")) {
  41.                                     writer.println(getSum(root));
  42.                             } else if (c.name.equals("add")) {
  43.                                     add(root, hm.get(c.x), c.x);
  44.                             } else {
  45.                                     delete(root, hm.get(c.x), c.x);
  46.                             }
  47.                     }
  48.             }
  49.  
  50.             void add(Node t, int u, long real) {
  51.                     int mid = (t.L + t.R) / 2;
  52.                     if (t.L == t.R) {
  53.                             t.sum[0] = real;
  54.                             t.cnt = 1;
  55.                     } else {
  56.                             if (u <= mid) {
  57.                                     add(t.l, u, real);
  58.                                     /*
  59.                                     long tmp = t.r.sum[4];
  60.                                     for (int i = 4; i > 0; --i)
  61.                                             t.r.sum[i] = t.r.sum[i - 1];
  62.                                     t.r.sum[0] = tmp;
  63.                                     */
  64.                             } else {
  65.                                     add(t.r, u, real);
  66.                             }
  67.                             t.cnt++;
  68.                             for (int i = 0; i < 5; ++i)
  69.                                     t.sum[i] = t.l.sum[i]
  70.                                                     + t.r.sum[((i - t.l.cnt % 5) % 5 + 5) % 5];
  71.                     }
  72.             }
  73.  
  74.             void delete(Node t, int u, long real) {
  75.                     int mid = (t.L + t.R) / 2;
  76.                     if (t.L == t.R) {
  77.                             t.sum[0] = 0;
  78.                             t.cnt = 0;
  79.                     } else {
  80.                             if (u <= mid) {
  81.                                     delete(t.l, u, real);
  82.                                     /*
  83.                                     long tmp = t.r.sum[0];
  84.                                     for (int i = 0; i < 4; ++i)
  85.                                             t.r.sum[i] = t.r.sum[i + 1];
  86.                                     t.r.sum[4] = tmp;
  87.                                     */
  88.                             } else {
  89.                                     delete(t.r, u, real);
  90.                             }
  91.                             t.cnt--;
  92.                             for (int i = 0; i < 5; ++i)
  93.                                     t.sum[i] = t.l.sum[i]
  94.                                                     + t.r.sum[((i - t.l.cnt % 5) % 5 + 5) % 5];
  95.                     }
  96.             }
  97.  
  98.             long getSum(Node t) {
  99.                     return t.sum[2];
  100.             }
  101.  
  102.             Node createTree(int L, int R) {
  103.                     Node t = new Node();
  104.                     t.sum = new long[5];
  105.                     t.cnt = 0;
  106.                     t.L = L;
  107.                     t.R = R;
  108.                     if (L < R) {
  109.                             int mid = (L + R) / 2;
  110.                             t.l = createTree(L, mid);
  111.                             t.r = createTree(mid + 1, R);
  112.                     }
  113.                     return t;
  114.             }
  115.  
  116.             class Node {
  117.                     Node l, r;
  118.                     long[] sum;
  119.                     int cnt, L, R;
  120.             }
  121.  
  122.             public static void main(String[] args) {
  123.                     new Thread(null, new D(), "", 64 * 1024 * 1024).run();
  124.             }
  125.  
  126.             BufferedReader reader;
  127.             StringTokenizer tokenizer;
  128.             PrintWriter writer;
  129.  
  130.             public void run() {
  131.                     try {
  132.                             try {
  133.                                     Locale.setDefault(Locale.US);
  134.                             } catch (Exception e) {
  135.                             }
  136.                             if (useStandardIO) {
  137.                                     reader = new BufferedReader(new InputStreamReader(System.in));
  138.                                     writer = new PrintWriter(System.out);
  139.                             } else {
  140.                                     reader = new BufferedReader(new FileReader(inFile));
  141.                                     writer = new PrintWriter(new FileWriter(outFile));
  142.                             }
  143.                             tokenizer = null;
  144.                             solve();
  145.                             reader.close();
  146.                             writer.close();
  147.                     } catch (Exception e) {
  148.                             e.printStackTrace();
  149.                             System.exit(1);
  150.                     }
  151.             }
  152.  
  153.             int nextInt() throws IOException {
  154.                     return Integer.parseInt(nextToken());
  155.             }
  156.  
  157.             long nextLong() throws IOException {
  158.                     return Long.parseLong(nextToken());
  159.             }
  160.  
  161.             double nextDouble() throws IOException {
  162.                     return Double.parseDouble(nextToken());
  163.             }
  164.  
  165.             BigInteger nextBigInteger() throws IOException {
  166.                     return new BigInteger(nextToken());
  167.             }
  168.  
  169.             String nextToken() throws IOException {
  170.                     while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  171.                             tokenizer = new StringTokenizer(reader.readLine());
  172.                     }
  173.                     return tokenizer.nextToken();
  174.             }
  175.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement