| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037881 |
2024-07-29T09:39:18 Z |
devariaota |
Addk (eJOI21_addk) |
C++17 |
|
312 ms |
18260 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long int ull;
const ll md = 1e9+7;
const int ukr = 1e6+10;
int read() {
int ketek = 0; bool ne=0;
register char c = getchar();
while(c == ' ' or c =='\n') c =getchar();
if(c=='-'){ne = 1; c = getchar();}
while(c >= '0' and c <='9') { ketek = (ketek<<3)+(ketek<<1)+c-'0'; c = getchar();}
if(ne) ketek*=-1;
return ketek;
}
void print(int x) {
if (x < 0) {putchar('-');x = -x;}
int len = 0, buf[10];
if (x == 0) {putchar('0');return;}
while (x > 0) {buf[len++] = x % 10; x/=10;}
while (len > 0) {putchar('0' + buf[--len]);}
}
void File_Work(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
int n, m, a, b, c, d, id;
struct babi{
ll x, y, id;
};
struct babis{
ll x, y;
};
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
ll pgkt(ll rnx, ll rny){
if(rny == 0) return 1;
ll nwrn = pgkt(rnx, rny/2);
if(rny%2){
return (((nwrn*nwrn)%md)*rnx)%md;
}else{
return (nwrn*nwrn)%md;
}
}
vector<int> v;
string s;
ll ar[ukr];
ll seg[ukr], seg2[ukr], seg3[ukr];
void upd(ll k, ll vl, ll rn, ll lx, ll rx){
if(lx == rx){
seg[rn] = vl;
return;
}
ll mid = (lx+rx)/2;
if(k <= mid){
upd(k, vl, 2*rn, lx, mid);
}else{
upd(k, vl, 2*rn+1, mid+1, rx);
}
seg[rn] = seg[2*rn] + seg[2*rn+1];
}
void upd2(ll k, ll vl, ll rn, ll lx, ll rx){
if(lx == rx){
seg2[rn] = (ll)vl*(k+1);
return;
}
ll mid = (lx+rx)/2;
if(k <= mid){
upd2(k, vl, 2*rn, lx, mid);
}else{
upd2(k, vl, 2*rn+1, mid+1, rx);
}
seg2[rn] = seg2[2*rn] + seg2[2*rn+1];
//cout << seg2[rn] << " " << rn << endl;
}
void upd3(ll k, ll vl, ll rn, ll lx, ll rx){
if(lx == rx){
seg3[rn] = vl*(n-k);
return;
}
ll mid = (lx+rx)/2;
if(k <= mid){
upd3(k, vl, 2*rn, lx, mid);
}else{
upd3(k, vl, 2*rn+1, mid+1, rx);
}
seg3[rn] = seg3[2*rn] + seg3[2*rn+1];
}
ll get(ll l, ll r, ll rn, ll lx, ll rx, ll *segts){
if(r < lx || rx < l){
return 0;
}
if(l <= lx && rx <= r){
return segts[rn];
}
ll mid = (lx+rx)/2;
return get(l, r, 2*rn, lx, mid, segts) + get(l, r, 2*rn+1, mid+1, rx, segts);
}
void solve(){
cin >> n >> m;
ll pw2 = 1;
while(n > pw2){
pw2 *= 2;
}
for(ll i = 0; i < n; i++){
cin >> ar[i];
upd(i, ar[i], 1, 0, pw2-1);
upd2(i, ar[i], 1, 0, pw2-1);
upd3(i, ar[i], 1, 0, pw2-1);
}
cin >> id;
while(id--){
cin >> a;
if(a == 1){
vector<int> tmp, tmp2;
for(int i = 0; i < m; i++){
cin >> b;
tmp.push_back(b-1);
tmp2.push_back(ar[b-1]);
}
for(int i = 1; i <= m; i++){
upd(tmp[i-1], tmp2[i%m], 1, 0, pw2-1);
upd2(tmp[i-1], tmp2[i%m], 1, 0, pw2-1);
upd3(tmp[i-1], tmp2[i%m], 1, 0, pw2-1);
ar[tmp[i-1]] = tmp2[i%m];
}
}else{
cin >> b >> c >> d;
b--; c--; d--;
ll ki = b+d;
ll ka = c-d;
if(ki > ka) swap(ki, ka);
ll kil = ki-b;
ll ans = 0;
//cout << b << " " << ki << " " << ka << " " << c << "\n";
/*
0 1 2 3 4 5 6 7
7 2 5 1 9 3 4 6
*/
ans += get(ki, ka, 1, 0, pw2-1, seg)*(kil+1);
ans += get(b, ki-1, 1, 0, pw2-1, seg2);
ans -= get(b, ki-1, 1, 0, pw2-1, seg)*b;
ans += get(ka+1, c, 1, 0, pw2-1, seg3);
ans -= get(ka+1, c, 1, 0, pw2-1, seg)*(n-c-1);
cout << ans << "\n";
/* 2 1
0 1 2 3 4 5
1 1 1
2 2 2
3 3 3
4 4 4
1 2 3 3 2 1
*/
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t =1;
//cin >> t;
for(int i = 1; i <= t; i++){
//cout << "Case " << i << ": ";
solve();
}
}
Compilation message
Main.cpp: In function 'int read()':
Main.cpp:10:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
10 | register char c = getchar();
| ^
Main.cpp: In function 'void File_Work()':
Main.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen("test.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6628 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
5 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
6 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
10 ms |
7004 KB |
Output is correct |
| 8 |
Correct |
9 ms |
6936 KB |
Output is correct |
| 9 |
Correct |
12 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
9564 KB |
Output is correct |
| 2 |
Correct |
41 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
57 ms |
12372 KB |
Output is correct |
| 4 |
Correct |
100 ms |
15680 KB |
Output is correct |
| 5 |
Correct |
153 ms |
16724 KB |
Output is correct |
| 6 |
Correct |
142 ms |
16468 KB |
Output is correct |
| 7 |
Correct |
143 ms |
16464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
13168 KB |
Output is correct |
| 2 |
Correct |
156 ms |
16208 KB |
Output is correct |
| 3 |
Correct |
312 ms |
18260 KB |
Output is correct |
| 4 |
Correct |
176 ms |
17000 KB |
Output is correct |
