task

Hello, there was a problem, the site for checking the solution gives an excess of the time limit. How and what can you optimize?

#include <iostream> #include <stack> #include <vector> using namespace std; int main() { long long i, n; cin >> n; stack <long long> A; stack <long long> B; vector <long long> C; for (i = 0 ; i < n ; i ++) { char x; long long X, k; cin >> x; switch ( x ) { case '+': { cin >> X; A.push (X); break; } case '-': { C.push_back (A.top ()); A.pop (); break; } case '?': { cin >> X; long long s=0; for (k=0 ; k<X ; k++) { s += A.top (); B.push (A.top ()); A.pop (); } C.push_back (s); for (k=0 ; k < X ; k++) { A.push (B.top ()); B.pop (); } break; } } } while (C.size() != 0) { cout << C[0] << endl; C.erase (C.begin ()); } }
  • C.erase (C.begin ()); Why not just remove the entire vector, and then completely remove it. Delete the first element in the vector for a very long time, because (if I remember correctly) it creates a new array and copies it. It is cheaper to remove from the end or the whole for (long long i = 0; i <C.size; ++ i) cout << C [i] << endl; C.clear (); - Valera Kvip
  • Without looking - since time does not pass, it’s not the code that needs to be optimized, but the algorithm must be changed ... - Harry
  • Replace the output simply by the elements did not change anything. But about the algorithm, the idea is good, I'll try to think of something, thanks! - zzronn
  • Is there a URL somewhere to log in and play? - Harry
  • Yes of course. Here is the site itself , there is a “Tasks” button on the left, there are a lot of tasks. And this is exactly the task - zzronn

1 answer 1

You need to store not only data, but also ready-made amounts - from zero to the current element. Then the desired amount is just as the difference of two values ​​...

Like that:

 #include <vector> #include <iostream> #include <numeric> #include <limits> using namespace std; struct Data { int val; long long sum; }; vector<Data> base{{0,0ll}}; int main() { int n; cin >> n; base.reserve(n); for(int i = 0; i < n; ++i) { cin.ignore(std::numeric_limits<std::streamsize>::max(),'\n'); char c; Data d; int k; cin.get(c); switch(c) { case '-': { cout << base.back().val << endl; base.pop_back(); break; } case '+': { cin >> d.val; d.sum = base.back().sum + d.val; base.push_back(d); break; } case '?': { cin >> k; cout << (base.back().sum - (base.end()-k-1)->sum) << endl; break; } } } }
  • Oooh, exactly, thanks a lot, now I'll just try to figure out the code. Thank you very much!! - zzronn