Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- import java.math.*;
- public class D implements Runnable {
- private final boolean useStandardIO = true;
- private final String inFile = ".in";
- private final String outFile = ".out";
- class Command {
- String name;
- int x;
- }
- private void solve() throws IOException {
- int n = nextInt();
- List<Command> cmds = new ArrayList<Command>();
- List<Integer> all = new ArrayList<Integer>();
- for (int i = 0; i < n; ++i) {
- String cmd = nextToken();
- Command c = new Command();
- if (cmd.equals("sum")) {
- } else {
- int x = nextInt();
- c.x = x;
- all.add(x);
- }
- c.name = cmd;
- cmds.add(c);
- }
- Collections.sort(all);
- Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
- int z = 0;
- for (int i = 0; i < all.size(); ++i)
- if (i == 0 || all.get(i) != all.get(i - 1)) {
- hm.put(all.get(i), z++);
- }
- Node root = createTree(0, hm.size());
- for (Command c : cmds) {
- if (c.name.equals("sum")) {
- writer.println(getSum(root));
- } else if (c.name.equals("add")) {
- add(root, hm.get(c.x), c.x);
- } else {
- delete(root, hm.get(c.x), c.x);
- }
- }
- }
- void add(Node t, int u, long real) {
- int mid = (t.L + t.R) / 2;
- if (t.L == t.R) {
- t.sum[0] = real;
- t.cnt = 1;
- } else {
- if (u <= mid) {
- add(t.l, u, real);
- /*
- long tmp = t.r.sum[4];
- for (int i = 4; i > 0; --i)
- t.r.sum[i] = t.r.sum[i - 1];
- t.r.sum[0] = tmp;
- */
- } else {
- add(t.r, u, real);
- }
- t.cnt++;
- for (int i = 0; i < 5; ++i)
- t.sum[i] = t.l.sum[i]
- + t.r.sum[((i - t.l.cnt % 5) % 5 + 5) % 5];
- }
- }
- void delete(Node t, int u, long real) {
- int mid = (t.L + t.R) / 2;
- if (t.L == t.R) {
- t.sum[0] = 0;
- t.cnt = 0;
- } else {
- if (u <= mid) {
- delete(t.l, u, real);
- /*
- long tmp = t.r.sum[0];
- for (int i = 0; i < 4; ++i)
- t.r.sum[i] = t.r.sum[i + 1];
- t.r.sum[4] = tmp;
- */
- } else {
- delete(t.r, u, real);
- }
- t.cnt--;
- for (int i = 0; i < 5; ++i)
- t.sum[i] = t.l.sum[i]
- + t.r.sum[((i - t.l.cnt % 5) % 5 + 5) % 5];
- }
- }
- long getSum(Node t) {
- return t.sum[2];
- }
- Node createTree(int L, int R) {
- Node t = new Node();
- t.sum = new long[5];
- t.cnt = 0;
- t.L = L;
- t.R = R;
- if (L < R) {
- int mid = (L + R) / 2;
- t.l = createTree(L, mid);
- t.r = createTree(mid + 1, R);
- }
- return t;
- }
- class Node {
- Node l, r;
- long[] sum;
- int cnt, L, R;
- }
- public static void main(String[] args) {
- new Thread(null, new D(), "", 64 * 1024 * 1024).run();
- }
- BufferedReader reader;
- StringTokenizer tokenizer;
- PrintWriter writer;
- public void run() {
- try {
- try {
- Locale.setDefault(Locale.US);
- } catch (Exception e) {
- }
- if (useStandardIO) {
- reader = new BufferedReader(new InputStreamReader(System.in));
- writer = new PrintWriter(System.out);
- } else {
- reader = new BufferedReader(new FileReader(inFile));
- writer = new PrintWriter(new FileWriter(outFile));
- }
- tokenizer = null;
- solve();
- reader.close();
- writer.close();
- } catch (Exception e) {
- e.printStackTrace();
- System.exit(1);
- }
- }
- int nextInt() throws IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws IOException {
- return Double.parseDouble(nextToken());
- }
- BigInteger nextBigInteger() throws IOException {
- return new BigInteger(nextToken());
- }
- String nextToken() throws IOException {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- tokenizer = new StringTokenizer(reader.readLine());
- }
- return tokenizer.nextToken();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement