結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-09 03:42:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 3,000 ms |
コード長 | 2,240 bytes |
コンパイル時間 | 854 ms |
コンパイル使用メモリ | 97,828 KB |
実行使用メモリ | 7,876 KB |
最終ジャッジ日時 | 2024-07-23 13:35:25 |
合計ジャッジ時間 | 5,797 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
/* -*- coding: utf-8 -*-** 1705.cc: No.1705 Mode of long array - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_M = 100000;const int MAX_E2 = 1 << 18; // = 262144/* typedef */typedef long long ll;typedef pair<ll,int> pli;template <typename T, const int MAX_E2>struct SegTreeMax {int e2;T nodes[MAX_E2], defv;SegTreeMax() {}void init(int n, T _defv) {defv = _defv;for (e2 = 1; e2 < n; e2 <<= 1);fill(nodes, nodes + MAX_E2, defv);}T &geti(int i) { return nodes[e2 - 1 + i]; }void seti(int i, T v) { geti(i) = v; }void setall() {for (int j = e2 - 2; j >= 0; j--)nodes[j] = max(nodes[j * 2 + 1], nodes[j * 2 + 2]);}void set(int i, T v) {int j = e2 - 1 + i;nodes[j] = v;while (j > 0) {j = (j - 1) / 2;nodes[j] = max(nodes[j * 2 + 1], nodes[j * 2 + 2]);}}T max_range(int r0, int r1, int k, int i0, int i1) {if (r1 <= i0 || i1 <= r0) return defv;if (r0 <= i0 && i1 <= r1) return nodes[k];int im = (i0 + i1) / 2;T v0 = max_range(r0, r1, k * 2 + 1, i0, im);T v1 = max_range(r0, r1, k * 2 + 2, im, i1);return max(v0, v1);}T max_range(int r0, int r1) { return max_range(r0, r1, 0, 0, e2); }};/* global variables */SegTreeMax<pli,MAX_E2> st;/* subroutines *//* main */int main() {ll n;int m;scanf("%lld%d", &n, &m);st.init(m, pli(0, -1));for (int i = 0; i < m; i++) {ll ai;scanf("%lld", &ai);st.seti(i, pli(ai, i));}st.setall();int qn;scanf("%d", &qn);while (qn--) {int ti, xi;ll yi;scanf("%d%d%lld", &ti, &xi, &yi), xi--;if (ti == 1) {pli v = st.geti(xi);st.set(xi, pli(v.first + yi, v.second));}else if (ti == 2) {pli v = st.geti(xi);st.set(xi, pli(v.first - yi, v.second));}else printf("%d\n", st.nodes[0].second + 1);}return 0;}