fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 200005;
  9.  
  10. long long bit[MAXN];
  11. int n;
  12.  
  13. void update(int idx, int delta) {
  14.     for (; idx <= n; idx += idx & -idx) {
  15.         bit[idx] += delta;
  16.     }
  17. }
  18.  
  19. long long query(int idx) {
  20.     long long sum = 0;
  21.     for (; idx > 0; idx -= idx & -idx) {
  22.         sum += bit[idx];
  23.     }
  24.     return sum;
  25. }
  26.  
  27. // Query for range [l, r]
  28. long long query_range(int l, int r) {
  29.     if (l > r) return 0;
  30.     return query(r) - query(l - 1);
  31. }
  32.  
  33. struct Ant {
  34.     long long d;
  35.     int type; // 1 for '+', -1 for '-'
  36.     int pos;
  37.     int original_idx;
  38. };
  39.  
  40. bool compareAnts(const Ant& a, const Ant& b) {
  41.     return a.d < b.d;
  42. }
  43.  
  44. int main() {
  45.     // Fast I/O
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.  
  49.     // Redirect file I/O
  50.     // freopen("GREETINGS.INP", "r", stdin);
  51.     // freopen("GREETINGS.OUT", "w", stdout);
  52.  
  53.     cin >> n;
  54.  
  55.     vector<Ant> ants(n);
  56.     vector<Ant> clockwise_ants;
  57.     vector<Ant> counter_clockwise_ants;
  58.  
  59.     for (int i = 0; i < n; ++i) {
  60.         char c;
  61.         long long d_val;
  62.         cin >> c >> d_val;
  63.         ants[i].d = d_val;
  64.         ants[i].pos = i + 1;
  65.         ants[i].original_idx = i + 1;
  66.         if (c == '+') {
  67.             ants[i].type = 1;
  68.             clockwise_ants.push_back(ants[i]);
  69.         } else {
  70.             ants[i].type = -1;
  71.             counter_clockwise_ants.push_back(ants[i]);
  72.         }
  73.     }
  74.  
  75.     sort(ants.begin(), ants.end(), compareAnts);
  76.  
  77.     vector<long long> ans(n + 1, 0);
  78.  
  79.     // Phase 1: Clockwise ants greet counter-clockwise ants
  80.     fill(bit, bit + n + 1, 0);
  81.     long long ccw_count = counter_clockwise_ants.size();
  82.     for (const auto& ant : counter_clockwise_ants) {
  83.         update(ant.pos, 1);
  84.     }
  85.  
  86.     for (const auto& current_ant : ants) {
  87.         if (current_ant.type == 1) { // Clockwise
  88.             long long dist = 2 * current_ant.d;
  89.             long long laps = dist / n;
  90.             long long rem = dist % n;
  91.  
  92.             long long greetings = laps * ccw_count;
  93.  
  94.             int start_pos = current_ant.pos;
  95.             int end_pos = start_pos + rem;
  96.  
  97.             if (end_pos > n) {
  98.                 greetings += query_range(start_pos + 1, n);
  99.                 greetings += query_range(1, end_pos % n);
  100.             } else {
  101.                 greetings += query_range(start_pos + 1, end_pos);
  102.             }
  103.             ans[current_ant.original_idx] += greetings;
  104.         } else { // Counter-clockwise ant finishes its journey
  105.             update(current_ant.pos, -1);
  106.             ccw_count--;
  107.         }
  108.     }
  109.  
  110.     // Phase 2: Counter-clockwise ants greet clockwise ants
  111.     fill(bit, bit + n + 1, 0);
  112.     long long cw_count = clockwise_ants.size();
  113.     for (const auto& ant : clockwise_ants) {
  114.         update(ant.pos, 1);
  115.     }
  116.  
  117.     for (const auto& current_ant : ants) {
  118.         if (current_ant.type == -1) { // Counter-clockwise
  119.             long long dist = 2 * current_ant.d;
  120.             long long laps = dist / n;
  121.             long long rem = dist % n;
  122.  
  123.             long long greetings = laps * cw_count;
  124.  
  125.             int start_pos = current_ant.pos;
  126.             // Cẩn thận với modulo số âm trong C++
  127.             long long end_pos_long = (long long)start_pos - rem; 
  128.             int end_pos;
  129.             if (end_pos_long <= 0) {
  130.                  end_pos = (end_pos_long % n + n) % n;
  131.                  if (end_pos == 0) end_pos = n; // 1-based index
  132.             } else {
  133.                 end_pos = end_pos_long;
  134.             }
  135.  
  136.             if (end_pos < start_pos) {
  137.                 greetings += query_range(end_pos, start_pos - 1);
  138.             } else { // Wrapped around
  139.                 greetings += query_range(end_pos, n);
  140.                 greetings += query_range(1, start_pos - 1);
  141.             }
  142.             ans[current_ant.original_idx] += greetings;
  143.         } else { // Clockwise ant finishes its journey
  144.             update(current_ant.pos, -1);
  145.             cw_count--;
  146.         }
  147.     }
  148.  
  149.     for (int i = 1; i <= n; ++i) {
  150.         cout << ans[i] << "\n";
  151.     }
  152.  
  153.     return 0;
  154. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
+4
-5
-5
+5
+5
-3
stdout
copy 
4
4
3
0
0
6
https://ideone.com/oph3ih
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!