Submission #311756

#	Time	Username	Problem	Language	Result	Execution time	Memory
311756		kaplanbar	Baloni (COCI15_baloni)	C++14	50 / 100	2100 ms	15188 KiB

baloni

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e6+5;
int n, a[N], nxt[N];
bool vis[N];
int find_next(int x) {
  if(!vis[nxt[x]]) return nxt[x];
  return nxt[x] = find_next(nxt[x]);   
}
void update(int x, int y) {
  assert(nxt[x] == y);
  nxt[x] = find_next(y);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    priority_queue<pair<int,int>> pq;
    for(int i = 0; i < n; i++) {
      cin >> a[i];
      nxt[i] = i + 1;
      pq.push(make_pair(a[i], i));
    }
    int c = 0;
    while(!pq.empty()) {
      int pos = pq.top().second;
      pq.pop();
      if(vis[pos]) {
        continue;
      }
      int cur = a[pos];
      int now = pos;
      while(now != n) {
        if(a[now] == cur) {
          cur--;
          vis[now] = 1;
          if(now != 0) update(now - 1, now);
        }
        now = find_next(now);
      }
      c++;
    }
    cout << c;
    return 0;
}

• Subtask 1: 50 / 100