結果
問題 |
No.833 かっこいい電車
|
ユーザー |
![]() |
提出日時 | 2019-05-31 02:25:49 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,978 bytes |
コンパイル時間 | 683 ms |
コンパイル使用メモリ | 86,364 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-02 03:55:17 |
合計ジャッジ時間 | 2,659 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:84:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 84 | scanf("%d%d", &n, &q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:91:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 91 | scanf("%d", &ai); | ~~~~~^~~~~~~~~~~ main.cpp:98:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 98 | scanf("%d%d", &op, &x); | ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 833.cc: No.833 かっこいい電車 - 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_N = 100000; /* typedef */ typedef long long ll; template <typename T, const int MAX_N> struct BIT { int n; T bits[MAX_N + 1]; BIT() {} void init(int _n) { n = _n; //memset(bits, 0, sizeof(bits)); } T sum(int x) { T s = 0; while (x > 0) { s += bits[x]; x -= (x & -x); } return s; } void add(int x, T v) { while (x <= n) { bits[x] += v; x += (x & -x); } } int lower_bound(T v) { int l = 0, r = n + 1; while (l + 1 < r) { int k = (l + r) / 2; if (sum(k) >= v) r = k; else l = k; } return r; } }; /* global variables */ BIT<int,MAX_N + 1> bit0; BIT<ll,MAX_N + 1> bit1; /* subroutines */ /* main */ int main() { int n, q; scanf("%d%d", &n, &q); bit0.init(n + 1); bit1.init(n + 1); for (int i = 1; i <= n; i++) { int ai; scanf("%d", &ai); bit0.add(i, 1); bit1.add(i, (ll)ai); } while (q--) { int op, x; scanf("%d%d", &op, &x); if (op == 1) { // connect if (bit0.sum(x) < bit0.sum(x + 1)) bit0.add(x + 1, -1); } else if (op == 2) { // separate if (bit0.sum(x) == bit0.sum(x + 1)) bit0.add(x + 1, 1); } else if (op == 3) { // remodel bit1.add(x, 1); } else { // attractiveness int k = bit0.sum(x); int i0 = bit0.lower_bound(k); int i1 = bit0.lower_bound(k + 1); //printf("x=%d, k=%d, i0,i1=%d,%d\n", x, k, i0, i1); printf("%lld\n", bit1.sum(i1 - 1) - bit1.sum(i0 - 1)); } } return 0; }