oj.uz

Submission #344925

# Submission time Handle Problem Language Result Execution time Memory
344925 2021-01-06T18:46:01 Z VROOM_VARUN Editor (BOI15_edi) C++14
100 / 100
 410 ms 80876 KB 
/*
ID: varunra2
LANG: C++
TASK: editor
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

struct segtree {
  VI st;
  int n;

  void init(int _n) {
    n = _n;
    st.assign(4 * n, INF);
  }

  void upd(int ind, int val, int l, int r, int node) {
    if (l > r) return;
    if (l > ind or r < ind) return;
    if (l == r) {
      st[node] = val;
      return;
    }
    int mid = (l + r) / 2;
    upd(ind, val, l, mid, 2 * node + 1);
    upd(ind, val, mid + 1, r, 2 * node + 2);
    st[node] = min(st[2 * node + 1], st[2 * node + 2]);
  }

  int qry(int val, int tl, int tr, int l, int r, int node) {
    if (l > r) return INF;
    if (l > tr or r < tl) return INF;
    if (st[node] >= val) return INF;
    if (l == r) {
      if (st[node] < val) return l;
      return INF;
    }

    int mid = (l + r) / 2;

    int valr = qry(val, tl, tr, mid + 1, r, 2 * node + 2);

    if (valr != INF) return valr;

    int vall = qry(val, tl, tr, l, mid, 2 * node + 1);
    assert(vall != INF);
    return vall;

    // if(l >= tl and r <= tr) {
    // int mid = (l + r)/2;
    // if(st[2 * node + 2] </ val) {
    // return qry(ind, val, tl, tr, mid + )
    // }
    // }
  }

  void upd(int ind, int val) { upd(ind, val, 0, n - 1, 0); }

  int qry(int ind, int val) { return qry(val, 0, ind - 1, 0, n - 1, 0); }
};

const int bits = 20;

int main() {
  // #ifndef ONLINE_JUDGE
  // freopen("editor.in", "r", stdin);
  // freopen("editor.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;

  segtree st;

  st.init(n + 1);

  st.upd(0, 0);
  VI ret(n + 1, 0);

  VVI lft(n + 1, VI(bits, 0));
  auto mn = lft;

  for (int i = 1; i <= n; i++) {
    int val;
    cin >> val;
    if (val > 0) {
      ret[i] = val;
      lft[i][0] = i;
    } else {
      val *= -1;
      int from = i - 1;
      for (int j = bits - 1; j >= 0; j--) {
        if (mn[from][j] >= val) from = lft[from][j];
      }
      lft[i][0] = from - 1;
      ret[i] = ret[from - 1];
      mn[i][0] = val;
      for (int j = 1; j < bits; j++) {
        lft[i][j] = lft[lft[i][j - 1]][j - 1];
        mn[i][j] = min(mn[i][j - 1], mn[lft[i][j - 1]][j - 1]);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    cout << ret[i] << '\n';
  }

  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1644 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 1644 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 1644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 80108 KB Output is correct
2 Correct 183 ms 80164 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40428 KB Output is correct
2 Correct 103 ms 48356 KB Output is correct
3 Correct 354 ms 63524 KB Output is correct
4 Correct 154 ms 80108 KB Output is correct
5 Correct 160 ms 80748 KB Output is correct
6 Correct 256 ms 78060 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 1644 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 1644 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 1664 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 1644 KB Output is correct
10 Correct 162 ms 80108 KB Output is correct
11 Correct 183 ms 80164 KB Output is correct
12 Correct 80 ms 40428 KB Output is correct
13 Correct 103 ms 48356 KB Output is correct
14 Correct 354 ms 63524 KB Output is correct
15 Correct 154 ms 80108 KB Output is correct
16 Correct 160 ms 80748 KB Output is correct
17 Correct 256 ms 78060 KB Output is correct
18 Correct 175 ms 80748 KB Output is correct
19 Correct 182 ms 80620 KB Output is correct
20 Correct 410 ms 79340 KB Output is correct
21 Correct 156 ms 80108 KB Output is correct
22 Correct 164 ms 80876 KB Output is correct