結果
問題 | No.510 二次漸化式 |
ユーザー | kotamanegi |
提出日時 | 2017-04-29 00:04:27 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 613 ms / 3,000 ms |
コード長 | 2,813 bytes |
コンパイル時間 | 1,052 ms |
コンパイル使用メモリ | 100,724 KB |
実行使用メモリ | 5,764 KB |
最終ジャッジ日時 | 2023-10-11 19:58:38 |
合計ジャッジ時間 | 12,003 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 149 ms
4,352 KB |
testcase_03 | AC | 149 ms
4,348 KB |
testcase_04 | AC | 148 ms
4,352 KB |
testcase_05 | AC | 148 ms
4,348 KB |
testcase_06 | AC | 566 ms
4,348 KB |
testcase_07 | AC | 546 ms
4,400 KB |
testcase_08 | AC | 545 ms
4,348 KB |
testcase_09 | AC | 548 ms
4,376 KB |
testcase_10 | AC | 27 ms
4,352 KB |
testcase_11 | AC | 27 ms
4,348 KB |
testcase_12 | AC | 28 ms
4,352 KB |
testcase_13 | AC | 27 ms
4,348 KB |
testcase_14 | AC | 27 ms
4,356 KB |
testcase_15 | AC | 28 ms
4,348 KB |
testcase_16 | AC | 125 ms
4,348 KB |
testcase_17 | AC | 118 ms
4,352 KB |
testcase_18 | AC | 122 ms
4,352 KB |
testcase_19 | AC | 116 ms
4,348 KB |
testcase_20 | AC | 121 ms
4,352 KB |
testcase_21 | AC | 120 ms
4,352 KB |
testcase_22 | AC | 120 ms
4,348 KB |
testcase_23 | AC | 613 ms
4,760 KB |
testcase_24 | AC | 607 ms
4,600 KB |
testcase_25 | AC | 590 ms
4,596 KB |
testcase_26 | AC | 582 ms
4,824 KB |
testcase_27 | AC | 573 ms
4,688 KB |
testcase_28 | AC | 590 ms
4,552 KB |
testcase_29 | AC | 583 ms
4,616 KB |
testcase_30 | AC | 588 ms
4,612 KB |
testcase_31 | AC | 412 ms
5,452 KB |
testcase_32 | AC | 425 ms
5,560 KB |
testcase_33 | AC | 146 ms
5,764 KB |
testcase_34 | AC | 37 ms
4,348 KB |
testcase_35 | AC | 36 ms
4,348 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include<map> #include <iomanip> #include <time.h> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> using namespace std; #define LONG_INF 10000000000000000 #define MAX_MOD 1000000007 #define REP(i,n) for(long long i = 0;i < n;++i) set<pair<long long, long long>> x; set<pair<long long, long long>> y; map<long long,long long> x_appear; map<long long,long long> y_appear; int main() { #define int long long long long n, query; cin >> n >> query; y.insert(make_pair(10000000, 0)); x.insert(make_pair(10000000, 0)); REP(test_case, query) { string s; cin >> s; if (s == "a") { long long a; cin >> a; auto xs = x.begin(); auto ys = y.begin(); long long ans = 1; long long back_b = 1; long long backed = 0; while (x.end() != xs&&y.end() != ys) { if (xs->first == ys->first) { if (xs->first <= a) { if (backed != ys->first - 1) { back_b = 1; } long long hoge = back_b*back_b; hoge %= MAX_MOD; hoge *= xs->second; hoge %= MAX_MOD; ans += hoge; ans %= MAX_MOD; backed = ys->first; back_b *= ys->second; back_b++; back_b %= MAX_MOD; xs++; ys++; } else break; } else if (xs->first < ys->first) { if (xs->first <= a) { if (backed != xs->first - 1) { back_b = 1; } long long hoge = back_b*back_b; hoge %= MAX_MOD; hoge *= xs->second; hoge %= MAX_MOD; ans += hoge; ans %= MAX_MOD; xs++; } else break; } else { if (ys->first <= a) { if (backed != ys->first - 1) { back_b = 1; } backed = ys->first; back_b *= ys->second; back_b++; back_b %= MAX_MOD; ys++; } else break; } } cout << ans%MAX_MOD << endl; } else if (s == "x") { int a, b; cin >> a >> b; if (x_appear[a] == 0) { x_appear[a] = 1; x.insert(make_pair(a+1, b)); } else { for (auto i = x.begin();i != x.end();++i) { int hoge = i -> first; if (hoge == a+1) { x.erase(i); x.insert(make_pair(a+1, b)); break; } } } } else { //s == "y" int a, b; cin >> a >> b; if (y_appear[a] == 0) { y_appear[a] = 1; y.insert(make_pair(a+1, b)); } else { for (auto i = y.begin();i != y.end();++i) { int hoge = i->first; if (hoge == a+1) { y.erase(i); y.insert(make_pair(a+1, b)); break; } } } } } }