| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 775022 |
2023-07-06T06:54:32 Z |
anhduc2701 |
Addk (eJOI21_addk) |
C++17 |
|
227 ms |
14280 KB |
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, k, q;
int a[maxn];
struct node
{
int s1, s2, len, sum;
node() {}
node(int x)
{
s1 = x;
s2 = x;
len = 1;
sum = x;
}
node operator+(const node &x)
{
node ans;
ans.s1 = x.sum * len + s1 + x.s1;
ans.s2 = sum * x.len + s2 + x.s2;
ans.sum = x.sum + sum;
ans.len = len + x.len;
return ans;
}
} st[maxn];
void build(int id, int l, int r)
{
if (l == r)
{
st[id] = node(a[l]);
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = st[id * 2] + st[id * 2 + 1];
}
void update(int id, int l, int r, int u, int val)
{
if (r < u || u < l)
return;
if (l == r)
{
st[id] = node(val);
return;
}
int mid = (l + r) / 2;
update(id * 2, l, mid, u, val);
update(id * 2 + 1, mid + 1, r, u, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
node get(int id, int l, int r, int u, int v)
{
if (u == l && r == v)
{
return st[id];
}
int mid = (l + r) / 2;
if (mid >= v)
return get(id * 2, l, mid, u, v);
if (mid < u)
return get(id * 2 + 1, mid + 1, r, u, v);
return get(id * 2, l, mid, u, mid) + get(id * 2 + 1, mid + 1, r, mid + 1, v);
}
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
build(1, 1, n);
cin >> q;
for (int i = 1; i <= q; i++)
{
int type;
cin >> type;
if (type == 1)
{
vector<int> pos;
for (int j = 1; j <= k; j++)
{
int vt;
cin >> vt;
pos.pb(vt);
}
update(1, 1, n, pos.back(), a[pos[0]]);
int vt = a[pos.back()];
a[pos.back()] = a[pos[0]];
for (int j = k - 2; j >= 0; j--)
{
update(1, 1, n, pos[j], vt);
int luu = vt;
vt = a[pos[j]];
a[pos[j]] = luu;
}
}
else
{
int l, r, m;
cin >> l >> r >> m;
/*
int sum = 0;
for (int i = l + m - 1; i <= r; i++)
{
for (int j = i - m + 1; j <= i; j++)
{
sum += a[j];
}
}
cout << sum << " ";
*/
int ans = 0;
if (r - l + 1 == m)
{
node k = get(1, 1, n, l, r);
cout << k.sum << "\n";
}
else
{
int d1 = min(l + m - 1, r - m + 1);
int d2 = max(d1 + 1, max(r - m + 1, l + m - 1));
ans += get(1, 1, n, l, d1).s1;
ans += get(1, 1, n, d2, r).s2;
if (d1 + 1 < d2)
{
ans += get(1, 1, n, d1 + 1, d2 - 1).sum * min(m, r - m + 1 - l + 1);
}
cout << ans << "\n";
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
4 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
724 KB |
Output is correct |
| 5 |
Correct |
4 ms |
724 KB |
Output is correct |
| 6 |
Correct |
6 ms |
980 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1072 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
2864 KB |
Output is correct |
| 2 |
Correct |
33 ms |
3276 KB |
Output is correct |
| 3 |
Correct |
46 ms |
5424 KB |
Output is correct |
| 4 |
Correct |
89 ms |
10256 KB |
Output is correct |
| 5 |
Correct |
124 ms |
13256 KB |
Output is correct |
| 6 |
Correct |
124 ms |
12968 KB |
Output is correct |
| 7 |
Correct |
114 ms |
13012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
5488 KB |
Output is correct |
| 2 |
Correct |
124 ms |
12600 KB |
Output is correct |
| 3 |
Correct |
227 ms |
14280 KB |
Output is correct |
| 4 |
Correct |
136 ms |
13472 KB |
Output is correct |
