oj.uz

Submission #979395

# Submission time Handle Problem Language Result Execution time Memory
979395 2024-05-10T19:14:34 Z Andrey Fish 3 (JOI24_fish3) C++14
100 / 100
 1474 ms 608604 KB 
#include<bits/stdc++.h>
using namespace std;

vector<long long> haha(300001);
vector<long long> wow(1200001);
vector<long long> bruh[12000001];
vector<long long> yay[1200001];
vector<long long> yeah[1200001];
long long sm = LLONG_MAX,ans = 0,d;

void build(long long l, long long r, long long x) {
    bruh[x].push_back(LLONG_MAX);
    yay[x].push_back(0);
    yeah[x].push_back(0);
    long long sb = 0,br = 0;
    for(long long i = r; i >= l; i--) {
        long long c = bruh[x][bruh[x].size()-1];
        long long f = 0;
        if(c < haha[i]) {
            f = (haha[i]-c+d-1)/d;
        }
        wow[x]+=f;
        bruh[x].push_back(haha[i]-f*d);
        long long e = haha[i]-f*d;
        if(c != LLONG_MAX) {
            br+=(c-e)/d;
        }
        yay[x].push_back(br);
        sb+=br;
        yeah[x].push_back(sb);
    }
    if(l == r) {
        return;
    }
    long long m = (l+r)/2;
    build(l,m,x*2);
    build(m+1,r,x*2+1);
}

void calc(long long l, long long r, long long x, long long ql, long long qr) {
    if(l == ql && r == qr) {
        if(sm < 0) {
            return;
        }
        long long bl = 0,br = bruh[x].size()-1;
        ans+=wow[x];
        if(sm >= bruh[x][1]) {
            sm = bruh[x][bruh[x].size()-1];
            return;
        }
        long long c = (bruh[x][1]-sm+d-1)/d;
        while(bl < br) {
            long long mid = (bl+br+1)/2;
            if(yay[x][mid] <= c) {
                bl = mid;
            }
            else {
                br = mid-1;
            }
        }
        ans+=c*bl-yeah[x][bl];
        sm = min(sm,bruh[x][bruh[x].size()-1]-d*(max(0LL,c-yay[x][bruh[x].size()-1])));
        return;
    }
    long long m = (l+r)/2;
    if(qr <= m) {
        calc(l,m,x*2,ql,qr);
    }
    else if(ql > m) {
        calc(m+1,r,x*2+1,ql,qr);
    }
    else {
        calc(m+1,r,x*2+1,m+1,qr);
        calc(l,m,x*2,ql,m);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,l,r;
    cin >> n >> d;
    for(long long i = 1; i <= n; i++) {
        cin >> haha[i];
    }
    cin >> q;
    build(1,n,1);
    for(long long i = 0; i < q; i++) {
        ans = 0;
        sm = LLONG_MAX;
        cin >> l >> r;
        calc(1,n,1,l,r);
        if(sm < 0) {
            cout << -1 << "\n";
        }
        else {
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 350096 KB Output is correct
2 Correct 85 ms 350288 KB Output is correct
3 Correct 80 ms 350324 KB Output is correct
4 Correct 87 ms 352140 KB Output is correct
5 Correct 85 ms 351876 KB Output is correct
6 Correct 84 ms 351320 KB Output is correct
7 Correct 92 ms 350932 KB Output is correct
8 Correct 85 ms 351956 KB Output is correct
9 Correct 84 ms 351856 KB Output is correct
10 Correct 86 ms 351828 KB Output is correct
11 Correct 89 ms 351864 KB Output is correct
12 Correct 85 ms 351820 KB Output is correct
13 Correct 84 ms 351828 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1216 ms 598164 KB Output is correct
2 Correct 943 ms 597928 KB Output is correct
3 Correct 183 ms 354904 KB Output is correct
4 Correct 837 ms 598428 KB Output is correct
5 Correct 853 ms 595508 KB Output is correct
6 Correct 876 ms 598040 KB Output is correct
7 Correct 866 ms 597072 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 358484 KB Output is correct
2 Correct 1474 ms 605252 KB Output is correct
3 Correct 1472 ms 604552 KB Output is correct
4 Correct 1446 ms 605820 KB Output is correct
5 Correct 1451 ms 604024 KB Output is correct
6 Correct 1292 ms 601860 KB Output is correct
7 Correct 1264 ms 597188 KB Output is correct
8 Correct 1276 ms 602564 KB Output is correct
9 Correct 1299 ms 600648 KB Output is correct
10 Correct 946 ms 601276 KB Output is correct
11 Correct 930 ms 599232 KB Output is correct
12 Correct 1309 ms 604268 KB Output is correct
13 Correct 1363 ms 606352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 515592 KB Output is correct
2 Correct 1160 ms 596188 KB Output is correct
3 Correct 561 ms 408344 KB Output is correct
4 Correct 1106 ms 602048 KB Output is correct
5 Correct 1164 ms 589372 KB Output is correct
6 Correct 1347 ms 604176 KB Output is correct
7 Correct 1107 ms 512928 KB Output is correct
8 Correct 1336 ms 603020 KB Output is correct
9 Correct 889 ms 595380 KB Output is correct
10 Correct 799 ms 596316 KB Output is correct
11 Correct 1072 ms 599448 KB Output is correct
12 Correct 1006 ms 600184 KB Output is correct
13 Correct 1283 ms 605676 KB Output is correct
14 Correct 859 ms 601244 KB Output is correct
15 Correct 1337 ms 604184 KB Output is correct
16 Correct 902 ms 598724 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 350096 KB Output is correct
2 Correct 85 ms 350288 KB Output is correct
3 Correct 80 ms 350324 KB Output is correct
4 Correct 87 ms 352140 KB Output is correct
5 Correct 85 ms 351876 KB Output is correct
6 Correct 84 ms 351320 KB Output is correct
7 Correct 92 ms 350932 KB Output is correct
8 Correct 85 ms 351956 KB Output is correct
9 Correct 84 ms 351856 KB Output is correct
10 Correct 86 ms 351828 KB Output is correct
11 Correct 89 ms 351864 KB Output is correct
12 Correct 85 ms 351820 KB Output is correct
13 Correct 84 ms 351828 KB Output is correct
14 Correct 1216 ms 598164 KB Output is correct
15 Correct 943 ms 597928 KB Output is correct
16 Correct 183 ms 354904 KB Output is correct
17 Correct 837 ms 598428 KB Output is correct
18 Correct 853 ms 595508 KB Output is correct
19 Correct 876 ms 598040 KB Output is correct
20 Correct 866 ms 597072 KB Output is correct
21 Correct 236 ms 358484 KB Output is correct
22 Correct 1474 ms 605252 KB Output is correct
23 Correct 1472 ms 604552 KB Output is correct
24 Correct 1446 ms 605820 KB Output is correct
25 Correct 1451 ms 604024 KB Output is correct
26 Correct 1292 ms 601860 KB Output is correct
27 Correct 1264 ms 597188 KB Output is correct
28 Correct 1276 ms 602564 KB Output is correct
29 Correct 1299 ms 600648 KB Output is correct
30 Correct 946 ms 601276 KB Output is correct
31 Correct 930 ms 599232 KB Output is correct
32 Correct 1309 ms 604268 KB Output is correct
33 Correct 1363 ms 606352 KB Output is correct
34 Correct 948 ms 515592 KB Output is correct
35 Correct 1160 ms 596188 KB Output is correct
36 Correct 561 ms 408344 KB Output is correct
37 Correct 1106 ms 602048 KB Output is correct
38 Correct 1164 ms 589372 KB Output is correct
39 Correct 1347 ms 604176 KB Output is correct
40 Correct 1107 ms 512928 KB Output is correct
41 Correct 1336 ms 603020 KB Output is correct
42 Correct 889 ms 595380 KB Output is correct
43 Correct 799 ms 596316 KB Output is correct
44 Correct 1072 ms 599448 KB Output is correct
45 Correct 1006 ms 600184 KB Output is correct
46 Correct 1283 ms 605676 KB Output is correct
47 Correct 859 ms 601244 KB Output is correct
48 Correct 1337 ms 604184 KB Output is correct
49 Correct 902 ms 598724 KB Output is correct
50 Correct 1436 ms 608604 KB Output is correct
51 Correct 1279 ms 599744 KB Output is correct
52 Correct 1238 ms 600660 KB Output is correct
53 Correct 925 ms 599228 KB Output is correct
54 Correct 1332 ms 602124 KB Output is correct
55 Correct 1448 ms 603976 KB Output is correct
56 Correct 837 ms 601756 KB Output is correct
57 Correct 867 ms 599596 KB Output is correct
58 Correct 831 ms 598940 KB Output is correct
59 Correct 1245 ms 603600 KB Output is correct
60 Correct 944 ms 601808 KB Output is correct
61 Correct 952 ms 598412 KB Output is correct
62 Correct 982 ms 600028 KB Output is correct
63 Correct 1332 ms 601656 KB Output is correct
64 Correct 849 ms 601412 KB Output is correct