# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
163936 | combi1k1 | Deda (COCI17_deda) | C++14 | 401 ms | 29188 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
const int N = 2e5 + 1;
namespace BIT2D {
vector<int> val[N];
vector<int> bit[N];
void ini() {
for(int i = 1 ; i < N ; ++i) {
sort(all(val[i]));
val[i].resize(unique(all(val[i])) - val[i].begin());
bit[i].assign(val[i].size() + 5,N);
}
}
void add(int x,int y) {
for(; x > 0 ; x -= x & -x)
val[x].push_back(y);
}
void upd(int x,int y,int v) {
for(; x > 0 ; x -= x & -x) {
int p = upper_bound(all(val[x]),y) - val[x].begin();
int K = bit[x].size();
for(; p < K ; p += p & -p)
bit[x][p] = min(bit[x][p],v);
}
}
int get(int x,int y) {
int ans = N;
for(; x < N ; x += x & -x) {
int p = upper_bound(all(val[x]),y) - val[x].begin();
for(; p > 0 ; p -= p & -p)
ans = min(ans,bit[x][p]);
}
return ans;
}
};
int t[N], s[N];
int a[N], b[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int q; cin >> q;
for(int i = 0 ; i < q ; ++i) {
char c; cin >> c; t[i] = (c == 'M');
cin >> b[i];
cin >> a[i];
if (t[i]) BIT2D::add(a[i],b[i]);
}
BIT2D::ini();
for(int i = 0 ; i < q ; ++i) {
if (t[i]) BIT2D::upd(a[i],b[i],a[i]);
else {
int res = BIT2D::get(a[i],b[i]);
if (res > n)
res = -1;
cout << res << "\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |