fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Kích thước tối đa cho mảng và cây BIT, cộng thêm 5 để an toàn
  9. const int MAXN = 200005;
  10.  
  11. // Cây Fenwick (BIT) và kích thước vòng tròn n
  12. long long bit[MAXN];
  13. int n;
  14.  
  15. // Cập nhật giá trị tại chỉ số idx bằng cách cộng thêm delta
  16. void update(int idx, int delta) {
  17.     for (; idx <= n; idx += idx & -idx) {
  18.         bit[idx] += delta;
  19.     }
  20. }
  21.  
  22. // Truy vấn tổng tiền tố từ 1 đến idx
  23. long long query(int idx) {
  24.     long long sum = 0;
  25.     for (; idx > 0; idx -= idx & -idx) {
  26.         sum += bit[idx];
  27.     }
  28.     return sum;
  29. }
  30.  
  31. // Truy vấn tổng trên đoạn [l, r]
  32. long long query_range(int l, int r) {
  33.     if (l > r) return 0;
  34.     return query(r) - query(l - 1);
  35. }
  36.  
  37. // Struct để lưu thông tin của một con kiến
  38. struct Ant {
  39.     long long d; // Quãng đường đi
  40.     int type;      // Hướng đi: 1 cho '+' (KĐH), -1 cho '-' (NKĐH)
  41.     int pos;       // Vị trí ban đầu (1-based)
  42.     int original_idx; // Chỉ số gốc để in kết quả đúng thứ tự
  43. };
  44.  
  45. // Hàm so sánh để sắp xếp các kiến theo quãng đường đi tăng dần
  46. bool compareAnts(const Ant& a, const Ant& b) {
  47.     return a.d < b.d;
  48. }
  49.  
  50. int main() {
  51.     // Tăng tốc độ nhập xuất
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.  
  55.     // Uncomment để đọc/ghi file
  56.     // freopen("GREETINGS.INP", "r", stdin);
  57.     // freopen("GREETINGS.OUT", "w", stdout);
  58.  
  59.     cin >> n;
  60.  
  61.     vector<Ant> ants(n);
  62.     vector<Ant> clockwise_ants; // Danh sách kiến đi KĐH (loại A)
  63.     vector<Ant> counter_clockwise_ants; // Danh sách kiến đi NKĐH (loại B)
  64.  
  65.     // Đọc dữ liệu và phân loại kiến
  66.     for (int i = 0; i < n; ++i) {
  67.         char c;
  68.         long long d_val;
  69.         cin >> c >> d_val;
  70.         ants[i].d = d_val;
  71.         ants[i].pos = i + 1;
  72.         ants[i].original_idx = i + 1;
  73.         if (c == '+') {
  74.             ants[i].type = 1;
  75.             clockwise_ants.push_back(ants[i]);
  76.         } else {
  77.             ants[i].type = -1;
  78.             counter_clockwise_ants.push_back(ants[i]);
  79.         }
  80.     }
  81.  
  82.     // "xét từ chú kiến có quãng đường đi ít nhất"
  83.     sort(ants.begin(), ants.end(), compareAnts);
  84.  
  85.     vector<long long> ans(n + 1, 0);
  86.  
  87.     // --- PHA 1: Tính lời chào từ kiến KĐH (loại A) đến kiến NKĐH (loại B) ---
  88.     fill(bit, bit + n + 1, 0); // Reset cây BIT
  89.     long long ccw_count = counter_clockwise_ants.size();
  90.     // Khởi tạo cây BIT quản lý các kiến NKĐH (loại B)
  91.     for (const auto& ant : counter_clockwise_ants) {
  92.         update(ant.pos, 1);
  93.     }
  94.  
  95.     // Duyệt qua các kiến theo thứ tự đã sắp xếp
  96.     for (const auto& current_ant : ants) {
  97.         if (current_ant.type == 1) { // Nếu kiến hiện tại là loại A (KĐH)
  98.             // Tính số lần nó "chủ động" chào các kiến loại B
  99.             long long dist = 2 * current_ant.d;
  100.             long long laps = dist / n;
  101.             long long rem = dist % n;
  102.  
  103.             // Chào trong các vòng hoàn chỉnh
  104.             long long greetings = laps * ccw_count;
  105.  
  106.             int start_pos = current_ant.pos;
  107.             int end_pos = start_pos + rem;
  108.  
  109.             // Chào trong quãng đường còn lại (rem)
  110.             // Dùng "query_range" để "trả lời có bao nhiêu chú kiến ngược chiều còn hiện diện"
  111.             if (end_pos > n) { // Trường hợp đi vòng qua mốc 0
  112.                 greetings += query_range(start_pos + 1, n);
  113.                 greetings += query_range(1, end_pos % n);
  114.             } else {
  115.                 greetings += query_range(start_pos + 1, end_pos);
  116.             }
  117.             ans[current_ant.original_idx] += greetings;
  118.  
  119.         } else { // Nếu kiến hiện tại là loại B (NKĐH), nó đã đi xong
  120.             // "loại bỏ nó khỏi vòng tròn"
  121.             update(current_ant.pos, -1);
  122.             ccw_count--;
  123.         }
  124.     }
  125.  
  126.     // --- PHA 2: Tính lời chào từ kiến NKĐH (loại B) đến kiến KĐH (loại A) ---
  127.     fill(bit, bit + n + 1, 0); // Reset cây BIT
  128.     long long cw_count = clockwise_ants.size();
  129.     // Khởi tạo cây BIT quản lý các kiến KĐH (loại A)
  130.     for (const auto& ant : clockwise_ants) {
  131.         update(ant.pos, 1);
  132.     }
  133.  
  134.     // Duyệt lại một lần nữa
  135.     for (const auto& current_ant : ants) {
  136.         if (current_ant.type == -1) { // Nếu kiến hiện tại là loại B (NKĐH)
  137.             // Tính số lần nó "chủ động" chào các kiến loại A
  138.             long long dist = 2 * current_ant.d;
  139.             long long laps = dist / n;
  140.             long long rem = dist % n;
  141.  
  142.             long long greetings = laps * cw_count;
  143.  
  144.             int start_pos = current_ant.pos;
  145.             long long end_pos_long = (long long)start_pos - rem;
  146.             int end_pos;
  147.  
  148.             // Xử lý cẩn thận vị trí khi đi ngược chiều (có thể < 1)
  149.             if (end_pos_long <= 0) {
  150.                  end_pos = (end_pos_long % n + n) % n;
  151.                  if (end_pos == 0) end_pos = n; // Vị trí 1-based
  152.             } else {
  153.                 end_pos = end_pos_long;
  154.             }
  155.  
  156.             // Dùng "query_range" để đếm số kiến KĐH trong khoảng
  157.             if (end_pos < start_pos) {
  158.                 greetings += query_range(end_pos, start_pos - 1);
  159.             } else { // Trường hợp đi vòng qua mốc 0 (ngược chiều)
  160.                 greetings += query_range(end_pos, n);
  161.                 greetings += query_range(1, start_pos - 1);
  162.             }
  163.             ans[current_ant.original_idx] += greetings;
  164.  
  165.         } else { // Nếu kiến hiện tại là loại A (KĐH), nó đã đi xong
  166.             // "loại bỏ nó khỏi vòng tròn"
  167.             update(current_ant.pos, -1);
  168.             cw_count--;
  169.         }
  170.     }
  171.  
  172.     // In kết quả cuối cùng theo thứ tự ban đầu
  173.     for (int i = 1; i <= n; ++i) {
  174.         cout << ans[i] << "\n";
  175.     }
  176.  
  177.     return 0;
  178. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
+4
-5
-5
+5
+5
-3
stdout
copy 
4
4
3
0
0
6
https://ideone.com/iiORPB
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!