oj.uz

Submission #108748

# Submission time Handle Problem Language Result Execution time Memory
108748 2019-05-01T08:23:46 Z MAMBA Editor (BOI15_edi) C++17
28 / 100
 400 ms 20608 KB 
// Wojtek Nadara
// Program wypisujacy tylko koncowy stan edytora
// Zlozonosc: O(n log n)
#include <bits/stdc++.h>
#include <vector>
#define MP make_pair
#define st first
#define nd second
using namespace std;
typedef pair<int, int> PII;
const int N = 5e5 + 5;
int nxt[N];
int prv[N];
int op[N];
void Del(int a) {
  nxt[prv[a]] = nxt[a];
  prv[nxt[a]] = prv[a];
}
int main() {
  ios_base::sync_with_stdio(0);
  int n;
  cin>>n;
  set<PII> by_lvl;
  by_lvl.insert(MP(0, 0));
  for (int i = 1; i <= n; i++) {
    cin>>op[i];
    if (op[i] < 0) {
      by_lvl.insert(MP(op[i], i));
    } else {
      by_lvl.insert(MP(0, -i));
    }
    nxt[i] = i + 1;
    prv[i] = i - 1;
  }
  prv[n + 1] = n;
  while (!by_lvl.empty()) {
    auto it = by_lvl.begin();
    auto most_important = *it;
    if (most_important.st == 0) {
      for(int i=1;i<n;i++)
		cout<<"0\n";
      cout<<op[-most_important.nd]<<"\n";
      return 0;
    }
    int to_undo = prv[most_important.nd];
    Del(most_important.nd);
    Del(to_undo);
    by_lvl.erase(most_important);
    if (op[to_undo] < 0) {
      by_lvl.erase(MP(op[to_undo], to_undo));
    } else {
      by_lvl.erase(MP(0, -to_undo));
    }
  }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 18680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 9768 KB Output is correct
2 Correct 106 ms 12456 KB Output is correct
3 Correct 108 ms 16744 KB Output is correct
4 Correct 177 ms 19960 KB Output is correct
5 Correct 400 ms 20608 KB Output is correct
6 Correct 161 ms 19320 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -