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;
}
Your solution O(N*T), at max N, T=2e5. At max O(1e7) allowed.
Can you reduce the check part to better than O(n)? O(log(n)) or O(1).
Can you do something with a map?? (insert, erase, size)
What do you think will be the rating of this problem in codeforces rating criteria?
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.
What do you think will be the rating of this problem in codeforces rating criteria?
maybe around 1000 — 1200.
that easy damn.. I thought I solved a hard one
probably like a 1000 and is a div 4 d atmost as well.
According to this AtCoder statistics website, it's a 422.
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...