Cod sursa(job #1827948)

Utilizator greenadexIulia Harasim greenadex Data 12 decembrie 2016 16:19:25
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
 
using namespace std;
 
const string name = "litere",
             in_file = name + ".in",
             out_file = name + ".out";
 
ifstream fin(in_file);
ofstream fout(out_file);
 
const int MAX = 1e4 + 5, SIGMA = 26;

int n;
int last[SIGMA];

char str[MAX];

int main() {
	fin >> n >> (str + 1);

	int sol = 0;
	for (int i = 1; i <= n; i++) {
		int letter = str[i] - 'a';

		if (!last[letter]) {
			last[letter] = 1;
			for (int j = letter - 1; j >= 0; j--) {
				if (last[j]) {
					last[letter] = last[j] + 1;
					break;
				} 
			}
		} else {
			last[letter]++;
		}

		for (int j = letter + 1; j < SIGMA; j++) {
			if (last[j]) {
				last[j]++;
			}
		}

		sol += (i - last[letter]);
	}

	fout << sol;
	return 0;
}