oj.uz

Submission #311756

# Submission time Handle Problem Language Result Execution time Memory
311756 2020-10-11T13:30:50 Z kaplanbar Baloni (COCI15_baloni) C++14
50 / 100
 2000 ms 15188 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 11 ms 512 KB Output is correct
5 Correct 1739 ms 13652 KB Output is correct
6 Execution timed out 2086 ms 15188 KB Time limit exceeded
7 Execution timed out 2097 ms 12772 KB Time limit exceeded
8 Execution timed out 2100 ms 12768 KB Time limit exceeded
9 Execution timed out 2100 ms 13140 KB Time limit exceeded
10 Execution timed out 2100 ms 13648 KB Time limit exceeded