結果
問題 | No.875 Range Mindex Query |
ユーザー | jupiro |
提出日時 | 2020-01-27 04:08:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,932 bytes |
コンパイル時間 | 1,271 ms |
コンパイル使用メモリ | 108,216 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-09-14 11:44:51 |
合計ジャッジ時間 | 6,171 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 328 ms
11,264 KB |
testcase_12 | AC | 271 ms
8,704 KB |
testcase_13 | AC | 258 ms
12,416 KB |
testcase_14 | AC | 249 ms
12,032 KB |
testcase_15 | AC | 346 ms
12,800 KB |
testcase_16 | AC | 331 ms
12,672 KB |
testcase_17 | AC | 345 ms
12,928 KB |
testcase_18 | AC | 334 ms
12,928 KB |
ソースコード
#include <cstdio>#include <iostream>#include <string>#include <sstream>#include <stack>#include <algorithm>#include <cmath>#include <queue>#include <map>#include <set>#include <cstdlib>#include <bitset>#include <tuple>#include <assert.h>#include <fstream>#include <bitset>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }const long long INF = 1LL << 60;const long long MOD = 1000000007LL;const long long MAX = 500000LL;using namespace std;typedef unsigned long long ull;typedef long long ll;struct SegmentTree {private:ll n;vector<ll> node;public:SegmentTree(vector<ll> v) {ll sz = v.size();n = 1; while (sz > n) n *= 2;node.resize(2 * n - 1, INF);for (ll i = 0; i < sz; i++) {node[i + n - 1] = v[i];}for (ll i = n - 2; i >= 0; i--) {node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);}}void update(ll x, ll val) {x += n - 1;node[x] = val;while (x > 0) {x = (x - 1) / 2;node[x] = min(node[x * 2 + 1], node[x * 2 + 2]);}}ll getmin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {if (r < 0) r = n;if (r <= a || b <= l) return INF;if (a <= l && r <= b) return node[k];ll vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);ll vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);return min(vl, vr);}};int main(){ll N, Q;cin >> N >> Q;vector<ll> a(N);map<ll, ll> mp;for (ll i = 0; i < N; i++) {cin >> a[i];mp[a[i]] = i;}SegmentTree seg(a);for (ll i = 0; i < Q; i++) {ll x, l, r;cin >> x >> l >> r;l--;r--;if (x == 1) {ll a = seg.getmin(l, l + 1);ll b = seg.getmin(r, r + 1);ll temp = mp[a];mp[a] = mp[b];mp[b] = temp;seg.update(l, b);seg.update(r, a);}else {cout << mp[seg.getmin(l, r + 1)] + 1 << '\n';}}return 0;}