oj.uz

Submission #475646

# Submission time Handle Problem Language Result Execution time Memory
475646 2021-09-23T14:59:15 Z Alex_tz307 Deda (COCI17_deda) C++17
0 / 140
 1000 ms 6876 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

struct SegTree {
  int Size;
  vector<int> tree;

  SegTree(int n) {
    Size = 1;
    while (Size < n) {
      Size <<= 1;
    }
    tree.resize(Size << 1, INF);
  }

  void update(int x, int lx, int rx, int pos, int val) {
    if (lx == rx) {
      tree[x] = val;
      cout << lx << ' ' << pos << ' ' << val << endl;
      return;
    }
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    if (pos <= mid) {
      update(lSon, lx, mid, pos, val);
    } else {
      update(rSon, mid + 1, rx, pos, val);
    }
    tree[x] = min(tree[lSon], tree[rSon]);
  }

  int query(int x, int lx, int rx, int pos, int val) {
    if (lx == rx) {
      return lx;
    }
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1, ans1 = INF, ans2 = INF;
    if (pos <= mid && tree[lSon] <= val) {
      ans1 = query(lSon, lx, mid, pos, val);
    }
    if (tree[rSon] <= val) {
      ans2 = query(rSon, mid + 1, rx, pos, val);
    }
    return min(ans1, ans2);
  }
};

void test_case() {
  int n, q;
  cin >> n >> q;
  SegTree tree(n);
  for (int i = 1; i <= q; ++i) {
    char op;
    int x, pos;
    cin >> op >> x >> pos;
    if (op == 'M') {
      tree.update(1, 1, n, pos, x);
    } else {
      int ans = tree.query(1, 1, n, pos, x);
      if (ans == INF) {
        ans = -1;
      }
      cout << ans << '\n';
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  for (int tc = 1; tc <= T; ++tc) {
    test_case();
  }
  return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 7 ms 332 KB Output isn't correct
4 Incorrect 317 ms 6876 KB Output isn't correct
5 Execution timed out 1092 ms 2636 KB Time limit exceeded
6 Execution timed out 1089 ms 3788 KB Time limit exceeded
7 Execution timed out 1067 ms 3580 KB Time limit exceeded