### comingsoon.cpp's blog

By comingsoon.cpp, history, 7 weeks ago,

Hello Guys.. I was trying to solve This atcoder problem From the last beginner contest but i was not able to come up with a working solution during the contest...After some upsolving, i finally came up with a solution that seems to work but the only problem is that it get's TLE on all the tests except the first three for which it passes and I don't know/understand why. This was the first ever ABC problem D that i have attempted after reading the problem statement.

This is the code below and I just need a little help or maybe come hints as to how to make it work because i can't think of a way to optimize it further.

#include <set>
#include <numeric>
#include <algorithm>
#include <vector>
#include <iostream>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;

int check(vector<int> a){
int q = a.size();
set<int> s; for(int i = 0; i < q; i++){
s.insert(a[i]);
}
return s.size();
}
void solve(){
int n , t; cin >> n >> t;
vector<int> mex; for(int i = 0; i < n; i++) mex.push_back(0);
for(int i = 0; i < t; i++){
int a, b; cin >> a >> b;
mex[a-1] += b;
cout << check(mex) << endl;
}
}
int main (){
ios::sync_with_stdio(false);
cin.tie(nullptr);
//ll t; cin >> t;
//for(;t--;){
solve();
//}
return 0;
}

• 0

 » 7 weeks ago, # |   +8 Hint 1Your solution O(N*T), at max N, T=2e5. At max O(1e7) allowed. Hint 2Can you reduce the check part to better than O(n)? O(log(n)) or O(1). Hint 3Can you do something with a map?? (insert, erase, size)
•  » » 7 weeks ago, # ^ |   0 What do you think will be the rating of this problem in codeforces rating criteria?
 » 7 weeks ago, # |   0 you are solving in O(N^2) this won't pass obviously. just use a frequency map and a set to keep track of distinct values. and insert a[i]+k and remove a[i] from the set if its frequency is 0 now. this is my submission to it. maybe look at it if you are stuck.
•  » » 7 weeks ago, # ^ |   0 What do you think will be the rating of this problem in codeforces rating criteria?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 maybe around 1000 — 1200.
•  » » » » 7 weeks ago, # ^ |   0 that easy damn.. I thought I solved a hard one
•  » » » 7 weeks ago, # ^ |   0 probably like a 1000 and is a div 4 d atmost as well.
•  » » » 7 weeks ago, # ^ |   0 According to this AtCoder statistics website, it's a 422.
 » 7 weeks ago, # |   0 It's pretty clear a set is difficult to implement with this, but there's another fast data structure you can use to keep track of different scores and the number of times they occur...