//srand(time(0)) - always changing
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;
int gcd(int a, int b) {
while (b) {
a %= b;
swap (a, b);
}
return a;
}
ll __sqrt(ll x) {
ll result = 0;
for (ll k = 1ll << 30; k != 0; k >>= 1) {
if ((result + k) * (result + k) <= x) {
result += k;
}
}
return result;
}
int a[N], ps[N], ss[N], sum[N];
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ps[i] = ps[i - 1] + a[i] * i;
sum[i] = sum[i - 1] + a[i];
}
for (int i = n; i > 0; i--) {
ss[i] = ss[i + 1] + a[i] * (n - i + 1);
}
int q;
cin >> q;
while (q--) {
int ty, l, r, m;
cin >> ty >> l >> r >> m;
if (ty == 1) continue;
int ln = r - l + 1;
if (ln < m * 2 - 1) {
int act = ln - m + 1;
int lmx = l + act - 2;
int rmx = r - act + 2;
int ans1 = (ps[lmx] - ps[l - 1]) - (sum[lmx] - sum[l - 1]) * (l - 1);
int ans2 = 0;
if (lmx + 1 <= rmx - 1) {
ans2 = (sum[rmx - 1] - sum[lmx]) * act;
}
int ans3 = (ss[rmx] - ss[r + 1]) - (sum[r] - sum[rmx - 1]) * (n - r);
cout << ans1 + ans2 + ans3 << '\n';
// cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';
} else {
int ans1 = 0;
if (m > 1) ans1 = (ps[l + m - 2] - ps[l - 1]) - (sum[l + m - 2] - sum[l - 1]) * (l - 1);
int ans2 = (sum[r] - sum[l - 1]) * m;
if (m > 1) ans2 = (sum[r - m + 1] - sum[l + m - 2]) * m;
int ans3 = 0;
if (m > 1) ans3 = (ss[r - m + 2] - ss[r + 1]) - (sum[r] - sum[r - m + 1]) * (n - r);
cout << ans1 + ans2 + ans3 << '\n';
// cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';
// cout << "ans3 = " << ss[r - m + 2] << ' ' << ss[r + 1] << ' ' << sum[r] << ' ' << sum[r - m + 1] << ' ' << n - r << '\n';
}
}
}
const bool Cases = 0;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TT = 1;
if (Cases) cin >> TT;
while (TT--) {
solve();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
1212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
2660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
