0

Could anybody help me find out how this could code run for more than 2 second ? Where 1 ≤ N ≤ 10^6 and 1 ≤ Q ≤ 2⋅10^5. Since push_back function to a vector have time complexity of O(1) and accessing from an unordered_map has also time complexity of O(1).

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;

bool check[1000000];

int main() {
    int N, Q, n;
    bool c = false;
    int last_reset[2] = {0,0};
    string Y;
    cin >> N >> Q;
    unordered_map<int,pair<int,int>> J;
    vector<int> H;
    for (short i = 0; i < Q; i++)
    {
        cin >> Y >> n;
        if(Y=="SET") m = 1;
        else if(Y=="RESTART") m = 2;
        else m = 3;
        switch (m)
        {
        case 1:
            cin >> u;
            check[n-1] = true;
            J[n] = {u,i+1};
            break;
        case 2:
            c = true;
            last_reset[0] = n;
            last_reset[1] = i+1;
            break;
        case 3:
            if (c && check[n-1] && last_reset[1] > J[n].second)
                H.push_back(last_reset[0]);
            else if (c && check[n-1] && last_reset[1] < J[n].second)
                H.push_back(J[n].first);
            else if(check[n-1] && !c)
                H.push_back(J[n].first);
            else if(!check[n-1] && c)
                H.push_back(last_reset[0]);
            else
                H.push_back(0);
            break;
        default:
            break;
        }
    }
    
    for (auto i:H)
        cout << i << endl;
    
    return 0;
}
Nahom Derese
  • 1
  • 1
  • 3
    "and accessing from a map has also time complexity of O(1)." thats not right. Anyhow complexitiy is about asymptotical behavior, it tells you little about runtime for a fixed input size – 463035818_is_not_an_ai Feb 04 '22 at 09:00
  • 3
    `std::vector` has *amortised* complexity of O(1) – you get exactly O(1) if you `reserve` enough space in advance, otherwise re-allocations might occur. Same for a hash map – but that is `std::unordered_map`, `std::map` is a *tree map* with complexity of O(log(n))... – Aconcagua Feb 04 '22 at 09:01
  • Also, you should use more descriptive variable names. Single letter names like `J`, `Y`, `H`, etc. makes the code hard to follow. – PaulMcKenzie Feb 04 '22 at 09:02
  • 1
    and to reproduce the issue you need to tell the input – 463035818_is_not_an_ai Feb 04 '22 at 09:03
  • 1
    If Q is large enough you run into an endless loop unless you are on a special machine with `short` having more than the typical 16 bit... – Aconcagua Feb 04 '22 at 09:04
  • 1
    `for (short i = 0; i < Q; i++)` -- `Q` is an `int`, but for some reason, you decided to make `i` a `short`. And please use the proper headers, not ``. – PaulMcKenzie Feb 04 '22 at 09:06
  • Side note: About [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – and much worse, [including `bits/stdc++.h`](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)... – Aconcagua Feb 04 '22 at 09:07
  • *Could anybody help me find out how this could code run for more than 2 second ?* -- How did you determine that this code runs for more than 2 seconds? – PaulMcKenzie Feb 04 '22 at 09:09
  • Side note about the *signed integer overflow* (`short`!) of `i` for large `Q`: Actually that's *undefined behaviour*! You could now be confronted with *anything* happening, though I don't know a system that in reality wouldn't just restart counting with -1 (as with *user* input compiler cannot predict in advance *if* UB really occurs – otherwise it might have eliminated the loop entirely, which whould have been legal in that case!). – Aconcagua Feb 04 '22 at 09:16
  • @Aconcagua yes using short i was the issue.....thanks for reminding – Nahom Derese Feb 05 '22 at 18:50

1 Answers1

0

for (short i = 0; i < Q; i++) -- Q is an int, but for some reason, I decided to make i a short, That was the problem that caused the error....

Nahom Derese
  • 1
  • 1