5AUnreviewed1000GPT-5.4 (high)

Chat Servers Outgoing Traffic

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Don't overcomplicate it: Add and Remove generate no traffic at all. So the final answer is just the sum of contributions from Send commands.

If there are currently $k$ people in the chat and someone sends a message of length $l$ , then the server sends that message to every participant, so this command contributes $k \cdot l$ bytes.

Because the input is guaranteed to be valid, you don't actually need to store the whole set of usernames. Tracking only the current number of users in the chat is enough. Yeah, a set would work too, but it'd be overkill for this tiny bastard.

Read input line by line using getline, because message texts may contain spaces. For a line of the form sender:message, the message length is simply the number of characters after the first :.

Maintain online and ans. For each line: if it starts with '+', do online++; if it starts with '-', do online--; otherwise find the colon position p and add

\text{online} \times (|s| - p - 1)

to the answer. Then print ans.

Key observation

This problem is pure simulation. No DP, no graph, no black magic—just don't screw up the parsing.

Only the Send command creates outgoing traffic. Add and Remove contribute exactly $0$ .

So the whole answer is:

\sum \bigl(\text{people currently in chat} \times \text{message length}\bigr)

over all Send commands.

What do we actually need to track?

At first glance you may think you need a set of usernames. You can do that, but honestly it's unnecessary.

Because the statement guarantees the input is correct:

no duplicate Add,
no invalid Remove,
senders are valid,

we only need the current number of people in the chat.

Let that be $online$ .

Then:

+name means $online \leftarrow online + 1$ ,
-name means $online \leftarrow online - 1$ ,
sender:message means add $online \times |message|$ to the answer.

Parsing detail that matters

Use getline, not cin >> ....

Why? Because messages may contain spaces, and can even be empty. A send command looks like:

\texttt{sender\_name:message\_text}

So for a line s, find the first colon at position $p$ . Then the message length is:

|s| - p - 1

That's it.

Algorithm

Initialize:

$online = 0$
$ans = 0$

For each input line s:

If s[0] == '+', increment $online$ .
Else if s[0] == '-', decrement $online$ .
Else it is a send command:
- find the position $p$ of :
- let $len = |s| - p - 1$
- do $ans \mathrel{+}= online \cdot len$

Finally print $ans$ .

Correctness sketch

We maintain the invariant that $online$ equals the number of users currently in the chat after processing each command.

For Add, exactly one user joins, so increasing $online$ by $1$ keeps the invariant true.
For Remove, exactly one user leaves, so decreasing $online$ by $1$ keeps the invariant true.
For Send, the server sends the message to all current participants, including the sender. If there are $online$ participants and the message length is $len$ , then the produced traffic is exactly $online \cdot len$ . Adding this to $ans$ is therefore correct.

Since every command is processed correctly, the final $ans$ is exactly the total outgoing traffic.

Complexity

Let $L$ be the total number of characters in the input.

Time: $O(L)$
Memory: $O(1)$

Which is hilariously more than enough for the limits.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s;
    ll online = 0, ans = 0;

    while (getline(cin, s)) {
        if (s.empty()) continue;

        if (s[0] == '+') {
            ++online;
        } else if (s[0] == '-') {
            --online;
        } else {
            size_t pos = s.find(':');
            ll len = (ll)s.size() - (ll)pos - 1;
            ans += online * len;
        }
    }

    cout << ans << '\n';
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    string s;
    ll online = 0, ans = 0;

    while (getline(cin, s)) {
        if (s.empty()) continue;

        if (s[0] == '+') {
            ++online;
        } else if (s[0] == '-') {
            --online;
        } else {
            size_t pos = s.find(':');
            ll len = (ll)s.size() - (ll)pos - 1;
            ans += online * len;
        }
    }

    cout << ans << '\n';
}

View on Codeforces Back to the list