Submission #1126879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126879		fryingduc	Deda (COCI17_deda)	C++20	20 / 140	109 ms	16124 KiB

deda

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, q;
map<int, int> bit[maxn];
void update(int x, int val) {
  for(int i = x; i > 0; i -= i & (-i)) {
    auto it = bit[i].lower_bound(val);
    if(it != bit[i].end() and it->second <= val) continue;
    it = bit[i].insert(it, make_pair(val, x));
    while(it != bit[i].begin()) {
      it--;
      if(it->second >= val) {
        it = bit[i].erase(it);
      } else break;
    }
  }
}
int get(int i, int val) {
  int res = 2e9;
  for(; i <= n; i += i & (-i)) {
    auto it = bit[i].upper_bound(val);
    if(it != bit[i].begin()) {
      it--;
      res = min(res, it->second);
    }
  } 
  return res;
}
void solve() {
  cin >> n >> q;
  while(q--) {
    char op; cin >> op;
    if(op == 'M') {
      int x, a; cin >> x >> a;
      update(a, x);
      
    } else {
      int y, b; cin >> y >> b;
      int res = get(b, y);
      cout << (res > 1e9 ? -1 : res) << '\n';
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0); 
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 20 / 140