oj.uz

Submission #1007702

# Submission time Handle Problem Language Result Execution time Memory
1007702 2024-06-25T10:57:29 Z phong Fire (JOI20_ho_t5) C++17
1 / 100
 237 ms 98120 KB 
    #include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 6e5 + 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 * 3];
        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 * 3];

        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 51800 KB Output is correct
2 Correct 5 ms 51804 KB Output is correct
3 Correct 5 ms 51804 KB Output is correct
4 Correct 5 ms 51804 KB Output is correct
5 Correct 4 ms 39516 KB Output is correct
6 Correct 6 ms 51804 KB Output is correct
7 Correct 5 ms 51704 KB Output is correct
8 Correct 6 ms 51804 KB Output is correct
9 Correct 6 ms 51804 KB Output is correct
10 Correct 6 ms 51804 KB Output is correct
11 Correct 4 ms 39516 KB Output is correct
12 Correct 6 ms 51804 KB Output is correct
13 Correct 6 ms 51616 KB Output is correct
14 Correct 6 ms 51804 KB Output is correct
15 Correct 5 ms 51804 KB Output is correct
16 Correct 5 ms 39516 KB Output is correct
17 Correct 5 ms 39516 KB Output is correct
18 Correct 5 ms 51804 KB Output is correct
19 Correct 6 ms 51804 KB Output is correct
20 Correct 5 ms 51804 KB Output is correct
21 Correct 4 ms 39416 KB Output is correct
22 Correct 6 ms 51804 KB Output is correct
23 Correct 5 ms 39516 KB Output is correct
24 Correct 5 ms 51700 KB Output is correct
25 Correct 5 ms 39516 KB Output is correct
26 Correct 4 ms 39516 KB Output is correct
27 Correct 5 ms 51804 KB Output is correct
28 Correct 4 ms 39464 KB Output is correct
29 Correct 5 ms 39516 KB Output is correct
30 Correct 6 ms 51740 KB Output is correct
31 Correct 6 ms 51804 KB Output is correct
32 Correct 5 ms 39516 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 51800 KB Output is correct
2 Correct 218 ms 98116 KB Output is correct
3 Incorrect 207 ms 98120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 51800 KB Output is correct
2 Incorrect 237 ms 92496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 51800 KB Output is correct
2 Correct 5 ms 51804 KB Output is correct
3 Correct 5 ms 51804 KB Output is correct
4 Correct 5 ms 51804 KB Output is correct
5 Correct 4 ms 39516 KB Output is correct
6 Correct 6 ms 51804 KB Output is correct
7 Correct 5 ms 51704 KB Output is correct
8 Correct 6 ms 51804 KB Output is correct
9 Correct 6 ms 51804 KB Output is correct
10 Correct 6 ms 51804 KB Output is correct
11 Correct 4 ms 39516 KB Output is correct
12 Correct 6 ms 51804 KB Output is correct
13 Correct 6 ms 51616 KB Output is correct
14 Correct 6 ms 51804 KB Output is correct
15 Correct 5 ms 51804 KB Output is correct
16 Correct 5 ms 39516 KB Output is correct
17 Correct 5 ms 39516 KB Output is correct
18 Correct 5 ms 51804 KB Output is correct
19 Correct 6 ms 51804 KB Output is correct
20 Correct 5 ms 51804 KB Output is correct
21 Correct 4 ms 39416 KB Output is correct
22 Correct 6 ms 51804 KB Output is correct
23 Correct 5 ms 39516 KB Output is correct
24 Correct 5 ms 51700 KB Output is correct
25 Correct 5 ms 39516 KB Output is correct
26 Correct 4 ms 39516 KB Output is correct
27 Correct 5 ms 51804 KB Output is correct
28 Correct 4 ms 39464 KB Output is correct
29 Correct 5 ms 39516 KB Output is correct
30 Correct 6 ms 51740 KB Output is correct
31 Correct 6 ms 51804 KB Output is correct
32 Correct 5 ms 39516 KB Output is correct
33 Correct 218 ms 98116 KB Output is correct
34 Incorrect 207 ms 98120 KB Output isn't correct
35 Halted 0 ms 0 KB -