Codeforces #366 Div.2 C. Thor
Question
問題要約
個のクエリが渡される クエリは以下の書式で渡される
t x
ここで,
- の時: アプリケーションが通知を生成する
- の時: アプリケーションが生成した通知をすべて読む (過去に読んだやつももう一度読む)
- の時: 生成された通知を, アプリケーション関係なく, 最初から数えて回目までのものをすべて読む.
各クエリ毎に, まだ読んでいない通知を出力する.
やること
以下の4つを用意する(少し冗長な気がする)
(は, アプリケーションの個数)
- app[アプリの番号]: 何個未読の通知を持っているか
- queue addedTime[アプリの番号]: いつ通知されたか
- memo[生成された順番]: なにが生成されたか
- sum: 現在の個数
この4つを実装し, 問題文のとおりに書くだけ 時間がギリギリなので.at()とかでアクセスしたらTLEした.
SourceCode
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> #include <array> #include <cmath> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define uinf 0x3f3f3f3f3f3f3f3f #define CLEAR(a) a = decltype(a)() #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define pii pair<int ,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define VVI vector<vector<int>> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define pi 2*acos(0.0) #define INFILE() freopen("in.txt","r",stdin) #define OUTFILE() freopen("out.txt","w",stdout) #define ll long long #define ull unsigned long long #define eps 1e-14 #define FIN std::ifstream cin("D:\input.txt") const int MOD = 1e9 + 7; signed int main(void) { ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector<int> app(N + 1); vector<queue<int>> addedTime(N + 1); vector<int> memo; memo.reserve(Q+1); int readtime = 0; int sum = 0; REP(i, Q) { int t, x; cin >> t >> x; if (t == 1) { memo.push_back(x); app[x]++; addedTime[x].push(memo.size()-1); ++sum; } if (t == 2) { sum -= app[x]; app[x] = 0; while (not addedTime[x].empty()) { int que = addedTime[x].front(); addedTime[x].pop(); memo[que] = 0; } } if (t == 3) { for (; readtime < x; ++readtime) { app[memo[readtime]]--; if(memo[readtime] != 0) --sum; } } cout << sum << endl; } return 0; }
感想
基本的にはやるだけ… のはずだった WAWAWAWAWA....
C++で書いたけど結構時間ギリギリになってしまった
2完で終わる悲しい結末になった