oj.uz

Submission #1007704

# Submission time Handle Problem Language Result Execution time Memory
1007704 2024-06-25T11:04:14 Z phong Fire (JOI20_ho_t5) C++17
100 / 100
 270 ms 118868 KB 
    #include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 8e5 + 1;
const ll oo = 1e9;
const int lg = 7, M = 4e3;
const int base = 2e5, mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;


int n, q, a[nmax];
namespace sub1{
    int rmq[nmax][lg + 1];
    int get(int l, int r){
        int k = __lg(r - l + 1);
        return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
    }
    void sol(){
        for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
        for(int j = 1; j <= lg; ++j){
            for(int i = 1; i + (1 << j) -1 <= n; ++i){
                rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
            }
        }

        while(q--){
            int t, l, r;
            cin >> t >> l >> r;
            ll ans = 0;
            for(int i = l; i <= r; ++i){
                ans += get(max(i - t, 1ll), i);
            }
            cout << ans << endl;
        }
    }
}
namespace sub2{
    int L[nmax], R[nmax];
    struct node{
        int l, i, r, id;
    };
    struct F1{
        ll f[nmax * 5];
        void update(int x, int val){
            x += 2 * n + 1;

            for(; x; x -= x&-x) f[x] += val;
        }
        ll get(int x){
            ll res = 0;
            x += 2 * n + 1;
            for(; x <= N;x += x&-x) res += f[x];
            return res;
        }
    }A[2], B[2], C[2],G[2];
    struct F2{
        ll f[nmax * 5];

        void update(int x, int val){
            x += 2 * n + 1;
            for(; x <= N; x += x&-x) f[x] += val;
        }
        ll get(int x){
            ll res = 0;
            x += 2 * n + 1;

            for(; x;x -= x&-x) res += f[x];
            return res;
        }
    }D[2], E[2];
    vector<node> adj[nmax];
    vector<pii> Q[nmax];
    int ans[nmax];
    void sol(){
        for(int i = 1; i <= n; ++i){
            L[i] = i - 1;
            while(L[i] > 0 && a[L[i]] < a[i]) L[i] = L[L[i]];
        }
        for(int i = n; i >= 1; --i){
            R[i]= i + 1;
            while(R[i] <= n && a[R[i]] <= a[i]) R[i] = R[R[i]];
        }
        for(int i = 1; i <= n; ++i){
            L[i]++;R[i]--;
            if(L[i] == 1) L[i] = -n;
            adj[i].push_back({L[i], i, R[i], 0});
            adj[R[i]].push_back({L[i], i, R[i], 1});
        }
        for(int e = 1; e <= q; ++e){
            int t, l, r;
            cin >> t >> l >> r;
            Q[r].push_back({t, e});
            Q[l - 1].push_back({t, -e});
        }
        for(int x = 1; x <= n; ++x){
            for(auto [l, i, r, id] : adj[x]){
                if(id == 0){
                    D[0].update(l - 1, (l - 1) * a[i]);
                    D[1].update(l - 1, a[i]);
                    E[0].update(i, i * a[i]);
                    E[1].update(i, a[i]);
                    G[0].update(i - l, (i - l) * a[i]);
                    G[1].update(i - l, a[i]);
                }
                else{
                    D[0].update(l - 1, -(l - 1) * a[i]);
                    D[1].update(l - 1, -a[i]);
                    E[0].update(i, -i * a[i]);
                    E[1].update(i, -a[i]);
                    G[0].update(i - l, -(i - l) * a[i]);
                    G[1].update(i - l, -a[i]);
                    //
                    A[0].update(r - l + 1, (r - l + 1) * a[i]);
                    A[1].update(r - l + 1, a[i]);
                    B[0].update(i - l, (i - l) * a[i]);
                    B[1].update(i - l, a[i]);
                    C[0].update(r - i, (r - i) * a[i]);
                    C[1].update(r - i, a[i]);
                }
            }
            for(auto [t, idx] : Q[x]){
                int id = abs(idx);
                int p;
                if(idx > 0) p = 1;
                else p = -1;

                int val = 0;
                t = min(t, x);
                val += A[0].get(t) - A[1].get(t) * t;
                val -= B[0].get(t) - B[1].get(t) * t;
                val -= C[0].get(t) - C[1].get(t) * t;
                //
                val += D[1].get(x - t) * (x - t)  - D[0].get(x - t);
                val -= E[1].get(x - t) * (x - t) - E[0].get(x - t);
                val -= G[0].get(t) - G[1].get(t) * t;
//                cout << x << ' ' << val << ' ' << p << endl;
                ans[id] += val * p;
            }
        }
        for(int i = 1; i <= q; ++i) cout << ans[i] << endl;
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//        freopen("code.inp", "r", stdin);
//        freopen("code.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sub2::sol();

}
/*
3 1
4 1 1
5 2 2




*/

Compilation message

ho_t5.cpp:149:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  149 | main(){
      | ^~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 56152 KB Output is correct
2 Correct 6 ms 55900 KB Output is correct
3 Correct 6 ms 55900 KB Output is correct
4 Correct 5 ms 55884 KB Output is correct
5 Correct 6 ms 43612 KB Output is correct
6 Correct 6 ms 55900 KB Output is correct
7 Correct 6 ms 55900 KB Output is correct
8 Correct 5 ms 55836 KB Output is correct
9 Correct 5 ms 55856 KB Output is correct
10 Correct 6 ms 55900 KB Output is correct
11 Correct 5 ms 43612 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55896 KB Output is correct
14 Correct 6 ms 55900 KB Output is correct
15 Correct 5 ms 55884 KB Output is correct
16 Correct 5 ms 43612 KB Output is correct
17 Correct 5 ms 43720 KB Output is correct
18 Correct 6 ms 55900 KB Output is correct
19 Correct 6 ms 55900 KB Output is correct
20 Correct 6 ms 55900 KB Output is correct
21 Correct 4 ms 43612 KB Output is correct
22 Correct 5 ms 55900 KB Output is correct
23 Correct 5 ms 43612 KB Output is correct
24 Correct 5 ms 55900 KB Output is correct
25 Correct 4 ms 43608 KB Output is correct
26 Correct 5 ms 43612 KB Output is correct
27 Correct 6 ms 55900 KB Output is correct
28 Correct 5 ms 43612 KB Output is correct
29 Correct 5 ms 43612 KB Output is correct
30 Correct 6 ms 55900 KB Output is correct
31 Correct 6 ms 55900 KB Output is correct
32 Correct 5 ms 43612 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 56152 KB Output is correct
2 Correct 214 ms 111952 KB Output is correct
3 Correct 201 ms 88404 KB Output is correct
4 Correct 203 ms 115588 KB Output is correct
5 Correct 209 ms 104528 KB Output is correct
6 Correct 216 ms 104272 KB Output is correct
7 Correct 227 ms 107092 KB Output is correct
8 Correct 186 ms 117588 KB Output is correct
9 Correct 224 ms 116048 KB Output is correct
10 Correct 205 ms 113612 KB Output is correct
11 Correct 245 ms 103256 KB Output is correct
12 Correct 204 ms 111188 KB Output is correct
13 Correct 212 ms 117500 KB Output is correct
14 Correct 203 ms 115328 KB Output is correct
15 Correct 205 ms 113488 KB Output is correct
16 Correct 224 ms 118644 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 56152 KB Output is correct
2 Correct 223 ms 99412 KB Output is correct
3 Correct 236 ms 93264 KB Output is correct
4 Correct 203 ms 107404 KB Output is correct
5 Correct 217 ms 97308 KB Output is correct
6 Correct 221 ms 101608 KB Output is correct
7 Correct 205 ms 99668 KB Output is correct
8 Correct 217 ms 106836 KB Output is correct
9 Correct 213 ms 97500 KB Output is correct
10 Correct 207 ms 92756 KB Output is correct
11 Correct 196 ms 96084 KB Output is correct
12 Correct 201 ms 97324 KB Output is correct
13 Correct 231 ms 107252 KB Output is correct
14 Correct 221 ms 112468 KB Output is correct
15 Correct 202 ms 99920 KB Output is correct
16 Correct 209 ms 106584 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 89224 KB Output is correct
2 Correct 205 ms 92344 KB Output is correct
3 Correct 192 ms 110668 KB Output is correct
4 Correct 194 ms 100532 KB Output is correct
5 Correct 243 ms 93112 KB Output is correct
6 Correct 197 ms 94392 KB Output is correct
7 Correct 211 ms 94876 KB Output is correct
8 Correct 228 ms 110788 KB Output is correct
9 Correct 214 ms 92496 KB Output is correct
10 Correct 243 ms 96696 KB Output is correct
11 Correct 222 ms 93368 KB Output is correct
12 Correct 228 ms 97824 KB Output is correct
13 Correct 229 ms 97456 KB Output is correct
14 Correct 217 ms 96696 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 56152 KB Output is correct
2 Correct 6 ms 55900 KB Output is correct
3 Correct 6 ms 55900 KB Output is correct
4 Correct 5 ms 55884 KB Output is correct
5 Correct 6 ms 43612 KB Output is correct
6 Correct 6 ms 55900 KB Output is correct
7 Correct 6 ms 55900 KB Output is correct
8 Correct 5 ms 55836 KB Output is correct
9 Correct 5 ms 55856 KB Output is correct
10 Correct 6 ms 55900 KB Output is correct
11 Correct 5 ms 43612 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55896 KB Output is correct
14 Correct 6 ms 55900 KB Output is correct
15 Correct 5 ms 55884 KB Output is correct
16 Correct 5 ms 43612 KB Output is correct
17 Correct 5 ms 43720 KB Output is correct
18 Correct 6 ms 55900 KB Output is correct
19 Correct 6 ms 55900 KB Output is correct
20 Correct 6 ms 55900 KB Output is correct
21 Correct 4 ms 43612 KB Output is correct
22 Correct 5 ms 55900 KB Output is correct
23 Correct 5 ms 43612 KB Output is correct
24 Correct 5 ms 55900 KB Output is correct
25 Correct 4 ms 43608 KB Output is correct
26 Correct 5 ms 43612 KB Output is correct
27 Correct 6 ms 55900 KB Output is correct
28 Correct 5 ms 43612 KB Output is correct
29 Correct 5 ms 43612 KB Output is correct
30 Correct 6 ms 55900 KB Output is correct
31 Correct 6 ms 55900 KB Output is correct
32 Correct 5 ms 43612 KB Output is correct
33 Correct 214 ms 111952 KB Output is correct
34 Correct 201 ms 88404 KB Output is correct
35 Correct 203 ms 115588 KB Output is correct
36 Correct 209 ms 104528 KB Output is correct
37 Correct 216 ms 104272 KB Output is correct
38 Correct 227 ms 107092 KB Output is correct
39 Correct 186 ms 117588 KB Output is correct
40 Correct 224 ms 116048 KB Output is correct
41 Correct 205 ms 113612 KB Output is correct
42 Correct 245 ms 103256 KB Output is correct
43 Correct 204 ms 111188 KB Output is correct
44 Correct 212 ms 117500 KB Output is correct
45 Correct 203 ms 115328 KB Output is correct
46 Correct 205 ms 113488 KB Output is correct
47 Correct 224 ms 118644 KB Output is correct
48 Correct 223 ms 99412 KB Output is correct
49 Correct 236 ms 93264 KB Output is correct
50 Correct 203 ms 107404 KB Output is correct
51 Correct 217 ms 97308 KB Output is correct
52 Correct 221 ms 101608 KB Output is correct
53 Correct 205 ms 99668 KB Output is correct
54 Correct 217 ms 106836 KB Output is correct
55 Correct 213 ms 97500 KB Output is correct
56 Correct 207 ms 92756 KB Output is correct
57 Correct 196 ms 96084 KB Output is correct
58 Correct 201 ms 97324 KB Output is correct
59 Correct 231 ms 107252 KB Output is correct
60 Correct 221 ms 112468 KB Output is correct
61 Correct 202 ms 99920 KB Output is correct
62 Correct 209 ms 106584 KB Output is correct
63 Correct 193 ms 89224 KB Output is correct
64 Correct 205 ms 92344 KB Output is correct
65 Correct 192 ms 110668 KB Output is correct
66 Correct 194 ms 100532 KB Output is correct
67 Correct 243 ms 93112 KB Output is correct
68 Correct 197 ms 94392 KB Output is correct
69 Correct 211 ms 94876 KB Output is correct
70 Correct 228 ms 110788 KB Output is correct
71 Correct 214 ms 92496 KB Output is correct
72 Correct 243 ms 96696 KB Output is correct
73 Correct 222 ms 93368 KB Output is correct
74 Correct 228 ms 97824 KB Output is correct
75 Correct 229 ms 97456 KB Output is correct
76 Correct 217 ms 96696 KB Output is correct
77 Correct 235 ms 109392 KB Output is correct
78 Correct 263 ms 110028 KB Output is correct
79 Correct 229 ms 113744 KB Output is correct
80 Correct 239 ms 107348 KB Output is correct
81 Correct 235 ms 112632 KB Output is correct
82 Correct 269 ms 107464 KB Output is correct
83 Correct 232 ms 100692 KB Output is correct
84 Correct 231 ms 113488 KB Output is correct
85 Correct 230 ms 113492 KB Output is correct
86 Correct 236 ms 110672 KB Output is correct
87 Correct 207 ms 114120 KB Output is correct
88 Correct 202 ms 115988 KB Output is correct
89 Correct 221 ms 105200 KB Output is correct
90 Correct 209 ms 102732 KB Output is correct
91 Correct 207 ms 105044 KB Output is correct
92 Correct 222 ms 94016 KB Output is correct
93 Correct 226 ms 107348 KB Output is correct
94 Correct 212 ms 113748 KB Output is correct
95 Correct 199 ms 108120 KB Output is correct
96 Correct 221 ms 105552 KB Output is correct
97 Correct 246 ms 94892 KB Output is correct
98 Correct 252 ms 115028 KB Output is correct
99 Correct 242 ms 115284 KB Output is correct
100 Correct 270 ms 118868 KB Output is correct
101 Correct 218 ms 115028 KB Output is correct
102 Correct 206 ms 117844 KB Output is correct