oj.uz

Submission #22980

# Submission time Handle Problem Language Result Execution time Memory
22980 2017-05-01T02:16:23 Z model_code Editor (BOI15_edi) C++11
28 / 100
 516 ms 22008 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() {
  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 0 ms 7884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 229 ms 22008 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 166 ms 14880 KB Output is correct
2 Correct 186 ms 16332 KB Output is correct
3 Correct 176 ms 19104 KB Output is correct
4 Correct 226 ms 22008 KB Output is correct
5 Correct 516 ms 22008 KB Output is correct
6 Correct 219 ms 22008 KB Output is correct

Subtask #4
0 / 37.0

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