fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int n, k;
  9.     if (!(cin >> n >> k)) return 0;
  10.     vector<int> a(k + 1);
  11.     int maxId = 0;
  12.     for (int i = 1; i <= k; ++i) {
  13.         cin >> a[i];
  14.         maxId = max(maxId, a[i]);
  15.     }
  16.  
  17.     // nextPos[i] = vị trí xuất hiện tiếp theo của a[i] sau i (hoặc INF)
  18.     vector<int> nextPos(k + 1, INF);
  19.     vector<int> lastOcc(maxId + 1, INF);
  20.     for (int i = k; i >= 1; --i) {
  21.         nextPos[i] = lastOcc[a[i]];
  22.         lastOcc[a[i]] = i;
  23.     }
  24.  
  25.     // Danh sách các id thực sự xuất hiện
  26.     vector<int> appears;
  27.     vector<char> seen(maxId + 1, 0);
  28.     for (int i = 1; i <= k; ++i) {
  29.         if (!seen[a[i]]) { appears.push_back(a[i]); seen[a[i]] = 1; }
  30.     }
  31.  
  32.     int m = maxId + 1;
  33.  
  34.     // pos[id] = bậc hiện tại của dụng cụ id (0..n)
  35.     vector<int> pos(m, 0);
  36.     // curNext[id] = chỉ số lần xuất hiện tiếp theo (hoặc INF)
  37.     vector<int> curNext(m, INF);
  38.     // init curNext bằng first occurrence (lastOcc currently chứa first occ after the build? we set below)
  39.     for (int id : appears) curNext[id] = lastOcc[id]; // lastOcc now holds first occurrence index
  40.  
  41.     // Mỗi bậc lưu set các cặp (nextOcc, id) sắp tăng dần. Muốn chọn evict = phần tử có next lớn nhất -> rbegin.
  42.     vector< set<pair<int,int>> > level(n + 1);
  43.     // Mỗi dụng cụ có iterator tới vị trí trong set để xóa nhanh
  44.     vector< set<pair<int,int>>::iterator > iterOf(m);
  45.  
  46.     // Khởi tạo: tất cả công cụ xuất hiện ban đầu ở level 0
  47.     for (int id : appears) {
  48.         auto it = level[0].insert({curNext[id], id}).first;
  49.         iterOf[id] = it;
  50.         pos[id] = 0;
  51.     }
  52.  
  53.     long long ops = 0;
  54.  
  55.     // Xử lý lần lượt các yêu cầu
  56.     for (int t = 1; t <= k; ++t) {
  57.         int x = a[t];
  58.  
  59.         // Cập nhật next cho công cụ x: từ next = t (đang dùng) -> nextPos[t]
  60.         // Xóa và chèn lại với khóa mới ở set của pos[x]
  61.         int oldNext = curNext[x];
  62.         int newNext = nextPos[t];
  63.         curNext[x] = newNext;
  64.         // remove old
  65.         level[pos[x]].erase(iterOf[x]);
  66.         // reinsert with new key
  67.         iterOf[x] = level[pos[x]].insert({curNext[x], x}).first;
  68.  
  69.         // Nếu đang ở bậc n thì đã sẵn sàng, không cần di chuyển
  70.         if (pos[x] == n) continue;
  71.  
  72.         // Di chuyển x dần lên đến bậc n
  73.         for (int l = pos[x]; l < n; ++l) {
  74.             // ensure we can insert into level l+1: if level[l+1] size == 2, evict one to l
  75.             if ((int)level[l+1].size() == 2) {
  76.                 // evict the one with largest curNext -> rbegin
  77.                 auto itEv = prev(level[l+1].end());
  78.                 int y_next = itEv->first;
  79.                 int y = itEv->second;
  80.                 // remove from l+1
  81.                 level[l+1].erase(itEv);
  82.                 // insert y into level l
  83.                 auto itIns = level[l].insert({curNext[y], y}).first;
  84.                 iterOf[y] = itIns;
  85.                 pos[y] = l;
  86.             }
  87.  
  88.             // Now move x from l -> l+1
  89.             // remove x from level l
  90.             level[l].erase(iterOf[x]);
  91.             // insert into level l+1
  92.             auto itNew = level[l+1].insert({curNext[x], x}).first;
  93.             iterOf[x] = itNew;
  94.             pos[x] = l + 1;
  95.  
  96.             ops += 1; // một thao tác cho mỗi bước cạnh
  97.         }
  98.         // x đã ở bậc n
  99.     }
  100.  
  101.     // Sau khi phục vụ xong các yêu cầu, phải chuyển tất cả về sàn (bậc 0)
  102.     // Mỗi dụng cụ ở bậc p cần p thao tác để xuống bậc 0 (có thể mô tả bằng cascade, tổng bằng tổng pos).
  103.     long long sumPos = 0;
  104.     for (int id : appears) sumPos += pos[id];
  105.     ops += sumPos;
  106.  
  107.     cout << ops << "\n";
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
3 12
1 2 3 2 1 4 2 1 1 2 1 3
stdout
copy 
25
https://ideone.com/FJfjHy
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!