Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O2")
- #include <bits/stdc++.h>
- #include <chrono>
- using namespace std;
- using ll = long long;
- using ull = unsigned long long;
- using ld = long double;
- #define Endl "\n"
- // Macros
- #define int long long
- // #define ll long long
- #define ld long double
- #define vt vector
- #define vi vector<int>
- #define vvi vector<vi>
- #define vii vector<pair<int,int>>
- #define pii pair<int,int>
- constexpr ll inf = 9e18;
- #define pb push_back
- #define em emplace_back
- #define all(X) (X).begin(), (X).end()
- #define allr(X) (X).rbegin(), (X).rend()
- #define sz(X) (int)X.size()
- #define each(x, a) for (auto &x: a)
- #define forn(i, n) for (int i = 0; i < n; ++i)
- #define forr(i, n) for (int i = n; i >=0; --i)
- #define rep(i,a,b) for(int i = a; i <= b; i++)
- // Debug macro
- string to_string(string s){return '"'+s+'"';}
- string to_string(const char* s){return to_string((string)s);}
- string to_string(const bool& b){return(b?"true":"false");}
- template<class T>string to_string(T x){ostringstream sout;sout<<x;return sout.str();}
- template<class A,class B>string to_string(pair<A,B> p){return "("+to_string(p.first)+", "+to_string(p.second)+")";}
- template<class A>string to_string(const vector<A> v){
- int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
- return res;
- }
- template<class A>string to_string(const set<A> v){
- int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
- return res;
- }
- template<class A, class B>string to_string(const map<A, B> v){
- int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
- return res;
- }
- template<class A>string to_string(const multiset<A> v){
- int f=1;string res="{";for(const auto x:v){if(!f)res+= ", ";f=0;res+=to_string(x);}res+="}";
- return res;
- }
- void debug_out(){puts("");}
- template<class T,class... U>void debug_out(const T& h,const U&... t){cerr<<" "<<to_string(h);debug_out(t...);}
- #ifndef ONLINE_JUDGE
- #define dbg(...) 233
- #else
- #define dbg(...) 233;
- #endif
- // Read
- template<typename T1, typename T2> // cin >> pair<T1, T2>
- istream& operator>>(istream &istream, pair<T1,T2> &p){ return (istream >> p.first >> p.second); }
- template<typename T> // cin >> vector<T>
- istream& operator>>(istream &istream, vector<T> &v){
- for(auto &it: v) cin >> it;
- return istream;
- }
- // Print
- template<typename T1, typename T2> // cout << pair<T1, T2>
- ostream& operator<<(ostream &ostream, const pair<T1, T2> &p){ return (ostream << p.first << " " << p.second); }
- template<typename T> //cout << vector<T>
- ostream& operator<<(ostream &ostream, const vector<T> &c){ for (auto &it: c) cout << it << " "; return ostream;}
- // Utility functions
- template<typename T>
- void print(T &&t) {cout << t << Endl;}
- template <typename T, typename... Args>
- void print(T &&t, Args &&... args){
- cout << t << " ";
- print(forward<Args>(args)...);
- }
- int n = -inf, m = -inf;
- void solve(){
- int k,i, j, q, x, y;
- k = i = j = q = x = y = n = m = -1;
- cin >> n;
- vi a(n+1);
- rep(i,1,n) cin >> a[i];
- vi pre(n+1);
- rep(i,1,n) pre[i] = pre[i-1]+a[i];
- vi pre2(n+1);
- rep(i,1,n) pre2[i] = pre2[i-1]+pre[i];
- dbg(pre);
- dbg(pre2);
- int ans = 0;
- auto calc = [&] (int i, int j){
- return pre2[j]-(pre2[i-1]+pre[i-1]*(j-i+1));
- };
- vi nsl(n+2);
- stack<int> st;
- // a.pb(-inf); // NOTICE
- pre.pb(-inf);
- st.push(n+1);
- for(i = n; i >= 0; i--){
- while(pre[st.top()] >= pre[i]){
- st.pop();
- }
- nsl[i] = st.top();
- st.push(i);
- }
- // int temp = calc(1,3);
- // dbg(temp);
- // dbg()
- rep(i,1,n){
- if(a[i] < 0) continue;
- int till = nsl[i-1]-1;
- ans += calc(i,till);
- dbg(i,till);
- // dbg(i,ans);
- }
- print(ans);
- }
- signed main(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- auto start = std::chrono::system_clock::now();
- #endif
- int t = 1;
- cin >> t;
- rep(tt, 1,t){
- // dbg(t);
- cout << "Case #" << tt << ": ";
- solve();
- #ifdef LOCAL
- auto end = std::chrono::system_clock::now();
- std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << Endl;
- #endif
- }
- #ifdef LOCAL
- auto end = std::chrono::system_clock::now();
- std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << Endl;
- cerr << "Completed" << Endl;
- #endif
- }
- /* stuff you should look for
- * constraints
- * int overflow, array bounds
- * special cases (n=1, n = 0?)
- * do smth instead of nothing and stay organized
- * WRITE STUFF DOWN
- * DON'T GET STUCK ON ONE APPROACH
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement