oj.uz

Submission #984018

# Submission time Handle Problem Language Result Execution time Memory
984018 2024-05-16T09:11:50 Z vjudge1 Snowball (JOI21_ho_t2) C++17
33 / 100
 2500 ms 7272 KB 
//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;



#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
template<class T>
int len(T &a){
    return a.size();
}

using ll = long long;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
string fileio = "";

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll infl = 1e18;
const int maxn = 1e5 + 1;





void solve(){
    ll n, q; cin >> n >> q;
    vector<ll> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i];
    vector<ll> nq;
    nq.push_back(0);
    ll s = 0;
    ll mn = 0, mx = 0;
    for(int i = 1; i <= q; i ++){
        ll x; cin >> x;
        s += x;
        if(s > mx) nq.push_back(s - mx), mx = s;
        if(s < mn) nq.push_back(s - mn), mn = s;
    }
    q = len(nq);
    vector<ll> lef(len(nq)), rig(len(nq));
    for(int i = 1; i < len(nq); i ++){
        lef[i] = lef[i - 1] + min(0ll, nq[i]);
        rig[i] = rig[i - 1] + max(0ll, nq[i]);
    }
    debug(nq);
    for(int i = 0; i < n; i ++){
        ll lb = -infl, rb = infl;
        if(i) lb = a[i - 1] - a[i];
        if(i + 1 < n) rb = a[i + 1] - a[i];
        //debug(lb, rb);
        ll ans = 0;
        for(int j = 1; j < q; j ++){
            if(nq[j] > 0) ans += max(0ll, min(rb, nq[j]));
            else ans += max(0ll, -max(lb, nq[j]));
            rb -= llabs(nq[j]); lb += llabs(nq[j]);
            //debug(lb, rb);
        }
        cout << ans << ' ';
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    auto start = chrono::high_resolution_clock::now();
    #ifndef LOCAL
    if(fileio.size()){
        freopen((fileio + ".in").c_str(), "r", stdin);
        freopen((fileio + ".out").c_str(), "w", stdout);
    }
    #endif
    int testcases = 1;
    #ifdef Tests
    cin >> testcases;
    #endif
    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else cout << '\n';
        cout << "_________________________" << endl;
        #endif
    }
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    
    cout << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:74:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
   74 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
Main.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen((fileio + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen((fileio + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 12 ms 348 KB Output is correct
6 Correct 8 ms 580 KB Output is correct
7 Correct 7 ms 472 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 1 ms 476 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 11 ms 592 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 12 ms 348 KB Output is correct
6 Correct 8 ms 580 KB Output is correct
7 Correct 7 ms 472 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 1 ms 476 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Correct 8 ms 604 KB Output is correct
17 Correct 11 ms 592 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 24 ms 7272 KB Output is correct
21 Correct 46 ms 6984 KB Output is correct
22 Correct 230 ms 7028 KB Output is correct
23 Correct 1958 ms 6892 KB Output is correct
24 Execution timed out 2531 ms 7076 KB Time limit exceeded
25 Halted 0 ms 0 KB -