oj.uz

Submission #493832

# Submission time Handle Problem Language Result Execution time Memory
493832 2021-12-13T05:57:12 Z i_am_noob Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 96 ms 5904 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pii pair<int,int>
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define inf 1000'000'000'000'000'000
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ": " << #__VA_ARGS__ << "- ",_do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ... S> void _do(T x, S ...y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif

const int maxn=200005;

int n,m,a[maxn],b[maxn];
deque<pii> dq;

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    rep(n) cin >> a[i];
    rep(n) cin >> b[i];
    if(n<=3000&&m<=3000){
        rep1(_,m){
            int s,t,u;
            cin >> s >> t >> u;
            s--,t--;
            dq.clear();
            dq.pb({0,u});
            int val=0;
            bool bad=0;
            rep3(i,t-1,s){
                if(a[i]>u){
                    bad=1;
                    break;
                }
                int to_delete=a[i];
                while(sz(dq)&&dq.back().second<=to_delete) to_delete-=dq.back().second,dq.pop_back();
                if(sz(dq)) dq.back().second-=to_delete;
                int to_add=a[i];
                while(sz(dq)&&dq.front().first>=b[i]){
                    val-=dq.front().first*dq.front().second;
                    to_add+=dq.front().second;
                    dq.pop_front();
                }
                dq.push_front({b[i],to_add});
                val+=b[i]*to_add;
            }
            if(bad){
                cout << "-1\n";
                continue;
            }
            cout << val << "\n";
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 476 KB Output is correct
2 Correct 32 ms 472 KB Output is correct
3 Correct 43 ms 516 KB Output is correct
4 Correct 51 ms 476 KB Output is correct
5 Correct 28 ms 484 KB Output is correct
6 Correct 38 ms 488 KB Output is correct
7 Correct 58 ms 456 KB Output is correct
8 Correct 29 ms 460 KB Output is correct
9 Correct 32 ms 528 KB Output is correct
10 Correct 49 ms 476 KB Output is correct
11 Correct 28 ms 596 KB Output is correct
12 Correct 40 ms 460 KB Output is correct
13 Correct 45 ms 588 KB Output is correct
14 Correct 47 ms 520 KB Output is correct
15 Correct 37 ms 508 KB Output is correct
16 Correct 35 ms 460 KB Output is correct
17 Correct 39 ms 472 KB Output is correct
18 Correct 20 ms 484 KB Output is correct
19 Correct 46 ms 488 KB Output is correct
20 Correct 96 ms 460 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 5904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 476 KB Output is correct
2 Correct 32 ms 472 KB Output is correct
3 Correct 43 ms 516 KB Output is correct
4 Correct 51 ms 476 KB Output is correct
5 Correct 28 ms 484 KB Output is correct
6 Correct 38 ms 488 KB Output is correct
7 Correct 58 ms 456 KB Output is correct
8 Correct 29 ms 460 KB Output is correct
9 Correct 32 ms 528 KB Output is correct
10 Correct 49 ms 476 KB Output is correct
11 Correct 28 ms 596 KB Output is correct
12 Correct 40 ms 460 KB Output is correct
13 Correct 45 ms 588 KB Output is correct
14 Correct 47 ms 520 KB Output is correct
15 Correct 37 ms 508 KB Output is correct
16 Correct 35 ms 460 KB Output is correct
17 Correct 39 ms 472 KB Output is correct
18 Correct 20 ms 484 KB Output is correct
19 Correct 46 ms 488 KB Output is correct
20 Correct 96 ms 460 KB Output is correct
21 Incorrect 9 ms 1868 KB Output isn't correct
22 Halted 0 ms 0 KB -