結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2022-11-12 01:09:50 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 256 ms / 3,000 ms |
コード長 | 1,558 bytes |
コンパイル時間 | 1,612 ms |
コンパイル使用メモリ | 143,816 KB |
実行使用メモリ | 10,716 KB |
最終ジャッジ日時 | 2024-09-13 17:57:08 |
合計ジャッジ時間 | 12,972 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;const ll MOD = 1000000007;struct Node {int x;ll cnt;int updated_at;Node(int x = -1, ll cnt = -1, int updated_at = -1) {this->x = x;this->cnt = cnt;this->updated_at = updated_at;}bool operator>(const Node &n) const {if (cnt == n.cnt) {return x < n.x;} else {return cnt < n.cnt;}}};int main() {ll N, M;cin >> N >> M;priority_queue <Node, vector<Node>, greater<Node>> pque;int time_table[M + 1];ll counter[M + 1];memset(time_table, 0, sizeof(time_table));for (int i = 1; i <= M; ++i) {ll a;cin >> a;counter[i] = a;pque.push(Node(i, a, 0));}int Q;cin >> Q;for (int i = 0; i < Q; ++i) {int t, x;ll y;cin >> t >> x >> y;// fprintf(stderr, "t: %d, x: %d, y: %lld\n", t, x, y);if (t == 1) {counter[x] += y;time_table[x]++;pque.push(Node(x, counter[x], time_table[x]));} else if (t == 2) {counter[x] -= y;time_table[x]++;pque.push(Node(x, counter[x], time_table[x]));} else {while (true) {Node node = pque.top();if (node.updated_at < time_table[node.x]) {pque.pop();} else {break;}}cout << pque.top().x << endl;}}return 0;}