oj.uz

Submission #528634

# Submission time Handle Problem Language Result Execution time Memory
528634 2022-02-20T22:41:23 Z Plurm Comparing Plants (IOI20_plants) C++11
27 / 100
 460 ms 19076 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
int lazy[1 << 19];
int sidx[1 << 19];
void build(int c, int l, int r) {
  lb[c] = l;
  rb[c] = r;
  sidx[c] = l;
  if (l == r)
    return;
  int k = (l + r) / 2;
  build(2 * c, l, k);
  build(2 * c + 1, k + 1, r);
}

void prop(int c) {
  if (lazy[c]) {
    seg[c] += lazy[c];
    if (lb[c] != rb[c]) {
      lazy[2 * c] += lazy[c];
      lazy[2 * c + 1] += lazy[c];
    }
    lazy[c] = 0;
  }
}

void update(int c, int l, int r, int x) {
  if (lb[c] == l && rb[c] == r)
    lazy[c] += x;
  prop(c);
  if (lb[c] == l && rb[c] == r)
    return;
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r) {
    update(2 * c, l, k, x);
    update(2 * c + 1, k + 1, r, x);
  } else if (r <= k) {
    update(2 * c, l, r, x);
    prop(2 * c + 1);
  } else {
    prop(2 * c);
    update(2 * c + 1, l, r, x);
  }
  if (seg[2 * c] <= seg[2 * c + 1]) {
    seg[c] = seg[2 * c];
    sidx[c] = sidx[2 * c];
  } else {
    seg[c] = seg[2 * c + 1];
    sidx[c] = sidx[2 * c + 1];
  }
}

pair<int, int> query(int c, int l, int r) {
  prop(c);
  if (lb[c] == l && rb[c] == r)
    return make_pair(seg[c], sidx[c]);
  int k = (lb[c] + rb[c]) / 2;
  if (l <= k && k < r)
    return min(query(2 * c, l, k), query(2 * c + 1, k + 1, r));
  else if (r <= k)
    return query(2 * c, l, r);
  else
    return query(2 * c + 1, l, r);
}

vector<int> h; // recovered
void init(int k, vector<int> r) {
  int n = r.size();
  h.resize(n, 0);
  build(1, 0, n - 1);
  for (int i = 0; i < n; i++) {
    update(1, i, i, r[i]);
  }
  for (int it = 0; it < n; it++) {
    int m = query(1, 0, n - 1).second;
    if (m + k < n) {
      auto p = query(1, m + k, n - 1);
      if (p.first == 0) {
        m = p.second;
      }
    }
    // printf("DBG %d\n", m);
    h[m] = n - it;
    if (m >= k - 1) {
      update(1, m - k + 1, m - 1, -1);
    } else {
      if (m != 0)
        update(1, 0, m - 1, -1);
      update(1, m + n - k + 1, n - 1, -1);
    }
    update(1, m, m, 1e9);
  }
}

int compare_plants(int x, int y) { return h[x] > h[y] ? 1 : -1; }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 51 ms 3432 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 65 ms 3448 KB Output is correct
11 Correct 49 ms 3444 KB Output is correct
12 Correct 49 ms 3652 KB Output is correct
13 Correct 50 ms 3572 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 51 ms 3432 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Correct 65 ms 3448 KB Output is correct
11 Correct 49 ms 3444 KB Output is correct
12 Correct 49 ms 3652 KB Output is correct
13 Correct 50 ms 3572 KB Output is correct
14 Correct 76 ms 4648 KB Output is correct
15 Correct 460 ms 15208 KB Output is correct
16 Correct 83 ms 6828 KB Output is correct
17 Correct 456 ms 18964 KB Output is correct
18 Correct 287 ms 18612 KB Output is correct
19 Correct 307 ms 19076 KB Output is correct
20 Correct 388 ms 19024 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 48 ms 3160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -