Submission #954388

#	Time	Username	Problem	Language	Result	Execution time	Memory
954388		vjudge1	Deda (COCI17_deda)	C++17	20 / 140	92 ms	11428 KiB

deda

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

void debug() {}
template<class T> void debug(T var) { cerr << var; }
template<class T, class ...P> void debug(T var, P ...t) { cerr << var << ", "; debug(t...); }
template<class T> void org(T l, T r) { while(l != r) cerr << *l++ << ' '; }
#define de(...) { cerr << "[Line: " << __LINE__ << "][" << #__VA_ARGS__ << "] -> [", debug(__VA_ARGS__), cerr << "]\n"; }
#define orange(...) { cerr << "[Line: " << __LINE__ << "][" << #__VA_ARGS__ << "] -> [", org(__VA_ARGS__), cerr << "]\n"; }
template<class T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct OP {
  bool t;
  int s, p, id, ans_id;
  OP() {}
  OP(bool _t, int _s, int _p, int _id, int _ans_id) : t(_t), s(_s), p(_p), id(_id), ans_id(_ans_id) {}
  friend bool operator<(const OP& a, const OP& b) {
    if(a.p == b.p)
      return a.id < b.id;
    return a.p < b.p;
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<OP> op; op.reserve(q);
  int ans_size = 0;
  for(int i = 0; i < q; ++i) {
    char c;
    int s, p;
    cin >> c >> p >> s;
    if(c == 'M')
      op.emplace_back(1, s, p, i, -1);
    else
      op.emplace_back(0, s, p, i, ans_size++);
    // op.emplace_back(c == 'M', s, p, ans_size++);
  }
  sort(op.begin(), op.end());
  set<int> st;
  vector<int> ans(ans_size, -1);
  for(int qid = 0; qid < q; ++qid) {
    // de(op[qid].t, op[qid].s, op[qid].p, op[qid].id);
    // orange(st.begin(), st.end());
    if(op[qid].t) {
      st.insert(op[qid].s);
    } else {
      auto it = st.lower_bound(op[qid].s);
      if(it != st.end())
        ans[op[qid].ans_id] = *it;
    }
  }
  for(auto& i : ans)
    cout << i << '\n';
}

int main() {
  cin.tie(0), ios_base::sync_with_stdio(0);

  int t = 1;
  // cin >> t;
  while(t--)
    solve();
}

• Subtask 1: 20 / 140