Answers will vary by airline.

AA will try to enroll you in the Gold (or Platinum) Challenge. These earn status faster than just flying but aren't quite a comp. You have to earn 5,000 (or 10,000) AA "qualifying points" in 90 days, starting the 1st or 16th of any month you choose. Q-points are 0.5 per mile for discount economy, 1.0 for full or near-full Y, up to 1.5 for paid F. You get a minimum of 500 Q-points per flight segment, which may help you.

Because they offer this option, AA is tight with comps, but it can be done. You'll have to provide a current competitive statement to prove your status. If the first agent you talk to won't offer a comp and insists on a challenge instead, don't push to the point where they put a note in your file. Sign off politely and try another one. (If you have a travel agent or corporate travel coordinator, they can probably make it happen through their AA sales rep.)

I don't know exactly what level "AC elite" corresponds to, or if you used it as a generic term, but AA will comp only its two lower tiers based on competitive status. You have to earn EXP yourself. There's no EXP Challenge, either.

For CO and others, somebody else?