Guest User

Untitled

a guest
Jul 7th, 2013
334
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.91 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.math.*;
  4. import java.awt.geom.*;
  5.  
  6. import static java.lang.Math.*;
  7.  
  8. public class Solution implements Runnable {
  9.  
  10.     public void solve() throws Exception {
  11.         int n = sc.nextInt();
  12.         String str = in.readLine();
  13.        
  14.         int[] balance = new int[n + 1];
  15.         for (int i = 0; i < n; i++) {
  16.             if (str.charAt(i) == 'a') {
  17.                 balance[i + 1] = balance[i] + 1;
  18.             } else {
  19.                 balance[i + 1] = balance[i] - 1;
  20.             }
  21.         }
  22.        
  23.         Arrays.sort(balance);
  24.        
  25.         long ans = 0;
  26.         for (int i = 0; i <= n; ) {
  27.             int j = i;
  28.             while (j <= n && balance[j] == balance[i]) {
  29.                 j++;
  30.             }
  31.             long cnt = j - i;
  32.             ans += cnt * (cnt - 1) / 2;
  33.             i = j;
  34.         }
  35.        
  36.         out.println(ans);
  37.     }
  38.  
  39.     static Throwable uncaught;
  40.  
  41.     BufferedReader in;
  42.     FastScanner sc;
  43.     PrintWriter out;
  44.  
  45.     @Override
  46.     public void run() {
  47.         try {
  48.             in = new BufferedReader(new InputStreamReader(System.in));
  49.             out = new PrintWriter(System.out);
  50.             sc = new FastScanner(in);
  51.             solve();
  52.         } catch (Throwable uncaught) {
  53.             Solution.uncaught = uncaught;
  54.         } finally {
  55.             out.close();
  56.         }
  57.     }
  58.  
  59.     public static void main(String[] args) throws Throwable {
  60.         Thread thread = new Thread(null, new Solution(), "", (1 << 26));
  61.         thread.start();
  62.         thread.join();
  63.         if (Solution.uncaught != null) {
  64.             throw Solution.uncaught;
  65.         }
  66.     }
  67.  
  68. }
  69.  
  70. class FastScanner {
  71.  
  72.     BufferedReader in;
  73.     StringTokenizer st;
  74.  
  75.     public FastScanner(BufferedReader in) {
  76.         this.in = in;
  77.     }
  78.  
  79.     public String nextToken() throws Exception {
  80.         while (st == null || !st.hasMoreTokens()) {
  81.             st = new StringTokenizer(in.readLine());
  82.         }
  83.         return st.nextToken();
  84.     }
  85.  
  86.     public int nextInt() throws Exception {
  87.         return Integer.parseInt(nextToken());
  88.     }
  89.  
  90.     public long nextLong() throws Exception {
  91.         return Long.parseLong(nextToken());
  92.     }
  93.  
  94.     public double nextDouble() throws Exception {
  95.         return Double.parseDouble(nextToken());
  96.     }
  97.  
  98. }
Advertisement
Add Comment
Please, Sign In to add comment