結果

問題 No.1705 Mode of long array
ユーザー Example0911
提出日時 2021-10-21 18:53:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 209 ms / 3,000 ms
コード長 3,527 bytes
コンパイル時間 2,026 ms
コンパイル使用メモリ 200,412 KB
最終ジャッジ日時 2025-01-25 02:28:27
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
#define int long long
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 1000000007;
/* RMQ[0,n-1]
set(int i, T x), build(): ixO(n)
update(i,x): i x O(log(n))
query(a,b): [a,b) O(log(n))
find_rightest(a,b,x): [a,b) xO(log(n))
find_leftest(a,b,x): [a,b) xO(log(n))
*/
template <typename T>
struct RMQ {
const T e = numeric_limits<T>::max();
function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };
int n;
vector<T> dat;
RMQ(int n_) : n(), dat(n_ * 4, e) {
int x = 1;
while (n_ > x) {
x *= 2;
}
n = x;
}
void set(int i, T x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
}
void update(int i, T x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return e;
}
else if (a <= l && r <= b) {
return dat[k];
}
else {
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
int find_rightest_sub(int a, int b, T x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // x or [a,b)[l,r)return a-1
return a - 1;
}
else if (k >= n - 1) { // return
return (k - (n - 1));
}
else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { // a-1 return
return vr;
}
else { // return
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
int find_leftest_sub(int a, int b, T x, int k, int l, int r) {
if (dat[k] > x || r <= a || b <= l) { // x or [a,b)[l,r)return b
return b;
}
else if (k >= n - 1) { // return
return (k - (n - 1));
}
else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { // b return
return vl;
}
else { // return
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M; cin >> N >> M;
RMQ<int>rmq(M);
for (int i = 0; i < M; i++) {
int a; cin >> a;
rmq.update(i, -a);
}
int Q; cin >> Q;
for (int i = 0; i < Q; i++) {
int T, X, Y; cin >> T >> X >> Y; X--;
if (T == 1) {
int now = rmq.query(X, X + 1);
rmq.update(X, now - Y);
}
else if (T == 2) {
int now = rmq.query(X, X + 1);
rmq.update(X, now + Y);
}
else {
int now = rmq.query(0, M);
cout << rmq.find_rightest(0, M, now) + 1 << endl;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0