結果
問題 |
No.2809 Sort Query
|
ユーザー |
|
提出日時 | 2024-04-21 19:55:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,957 bytes |
コンパイル時間 | 6,199 ms |
コンパイル使用メモリ | 254,712 KB |
最終ジャッジ日時 | 2025-02-21 08:23:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 53 WA * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:44:14: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=] 44 | scanf("%ld", &x); | ~~^ ~~ | | | | | long long int* | long int* | %lld main.cpp:57:18: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 3 has type ‘long long int*’ [-Wformat=] 57 | scanf("%d%ld", &k, &x); | ~~^ ~~ | | | | | long long int* | long int* | %lld main.cpp:81:19: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘std::unordered_map<int, long long int>::mapped_type’ {aka ‘long long int’} [-Wformat=] 81 | printf("%ld\n", m2[k]); | ~~^ | | | long int | %lld main.cpp:85:19: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘long long int’ [-Wformat=] 85 | printf("%ld\n", *p); | ~~^ ~~ | | | | | long long int | long int | %lld main.cpp:36:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 36 | scanf("%d%d", &n, &q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | scanf("%ld", &x); | ~~~~~^~~~~~~~~~~ main.cpp:52:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-
ソースコード
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; struct segtree{ int n; vector<int> dat; segtree(int _n):n(_n){ dat.resize(2*n); } void update(int i, int c){ i += n; dat[i] = c; i /= 2; while(i){ dat[i] = dat[2*i] + dat[2*i+1]; i /= 2; } } int sum(int l, int r){ l += n; r += n; int ret = 0; while(l < r){ if(l & 1) ret += dat[l++]; if(r & 1) ret += dat[--r]; l /= 2, r /= 2; } return ret; } }; int main(){ int n, q; scanf("%d%d", &n, &q); //assert(1 <= n && n <= 500000 && 1 <= q && q <= 500000); tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> m; segtree ch(n); unordered_map<int, long long> m2; long long check_x = 0; for(int i = 0; i < n; i++){ long long x; scanf("%ld", &x); //assert(1 <= x && x <= 1000000000000000000LL); //assert(check_x <= x); check_x = x; m.insert(x); } while(q--){ int type; scanf("%d", &type); //assert(1 <= type && type <= 3); if(type == 1){ int k; long long x; scanf("%d%ld", &k, &x); //assert(1 <= k && k <= n && 1 <= x && x <= 1000000000000000000LL); k--; if(m2.count(k)){ m2[k] = x; }else{ m2[k] = x; ch.update(k, 1); int c = ch.sum(0, k); auto p = m.find_by_order(k - c); m.erase(p); } }else if(type == 2){ for(auto [p, q] : m2){ ch.update(p, 0); m.insert(q); } m2.clear(); }else{ int k; scanf("%d", &k); //assert(1 <= k && k <= n); k--; if(m2.count(k)){ printf("%ld\n", m2[k]); }else{ int c = ch.sum(0, k); auto p = m.find_by_order(k - c); printf("%ld\n", *p); } } } }