oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

appeal Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Guan is trying to pursue a degree in English Literature. Since Guan is horrible at ELit, he is trying to write a letter of appeal to the University in order to apply for the degree. Guan, being horribly uncreative, only has N words in his appeal letter and all these N words are made of small letters that are less than 10 characters long, seperated by only spaces and without punctuation.

However, Guan knows something most people don't about the system. He knows that the machine that takes in the letters of appeal and rates them by a "reliability" rating. This reliability rating is the number of "reliable" word pairs there are in the letter.

A pair of words i and j are reliable if and only if word i is lexicographically smaller than word j and i < j. For example, ("apple", "bear") is reliable, ("aeroplane", "apple") is reliable and ("bear, banana") is not.

Guan writes out a letter and prepares it to submit it to the University. Help Guan calculate its "reliability" rating.

Subtasks

Subtask 1 (14%): 1 ≤ N ≤ 100. The words will not be more than 5 letters long.
Subtask 2 (25%): 1 ≤ N ≤ 100.
Subtask 3 (28%): 1 ≤ N ≤ 1000.
Subtask 4 (33%): 1 ≤ N ≤ 100000.

Input

The first line of input will contain one integer, N.
The next line of input will contain N words, as mentioned above.

Output

The output should consist of one line, stating the reliability rating of the letter.

Sample Input

5
i really love apple pies

Sample Output

5

Explanation

(i, really), (i, love), (i, pies), (love, pies), (apple, pies) are "reliable" word pairs.

Tags

Data Structure, Fenwick

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
114201s64MBMinimum
225301s64MBMinimum
328431s64MBMinimum
433493s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o appeal -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.