| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581593 |
2022-06-22T19:55:16 Z |
TimDee |
Addk (eJOI21_addk) |
C++14 |
|
1310 ms |
12296 KB |
#include <bits/stdc++.h>
using namespace std;
#define paiu return
#define moment 0;
#define int long long
#define ll long long
#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)
#define forrr(i,j,x) for (int i=j; i<x; i++)
#define di(a,n) deque<int> a(n,0)
#define dll(a,n) deque<ll> a(n,0)
#define vi(a,n) vector<int> a(n,0)
#define vll(a,n) vector<ll> a(n,0)
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
int n=a.size();
vi(pr,n+1);
forn(i,n) pr[i+1]=pr[i]+a[i];
return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
#define f first
#define s second
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;
struct segtree {
vector<int> tree;
vector<pi> addtree;
int size;
int n;
int neutral;
void put(int i, int v) {
tree[i]=v;
addtree[i]={v,1};
}
int combine(int i, int j) {
//for min
//return min(i,j);
//for max
//return max(i,j);
//for sum
return i+j;
}
pi addcombine(pi a, pi b, int lb, int rb) {
return {a.f+(b.s!=0)*a.s*query(lb,rb)+b.f,a.s+b.s};
}
void update(int x, int l, int r, int i) {
if (i>=r || i<l) return;
if (r-l == 1) return;
int mid=(l+r)/2;
update(2*x+1,l,mid,i);
update(2*x+2,mid,r,i);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
addtree[x]=addcombine(addtree[2*x+1],addtree[2*x+2],mid,r);
}
void update(int x, int l, int r) {
if (r-l == 1) return;
int mid=(l+r)/2;
update(2*x+1,l,mid);
update(2*x+2,mid,r);
tree[x]=combine(tree[2*x+1],tree[2*x+2]);
addtree[x]=addcombine(addtree[2*x+1],addtree[2*x+2],mid,r);
}
segtree(vector<int>&a, int neutr) {
n=a.size();
//for min
//neutral = inf;
//for max
//neutral = -inf;
//for sum
//neutral = 0;
neutral = neutr;
size=1;
while (size < n) size*=2;
tree.assign(2*size-1,neutral);
addtree.assign(2*size-1,{neutral,0});
forr(i,n) put(size-1+i,a[i]);
update(0,0,size);
}
void clear() {
tree.assign(2*size-1,0);
}
int calc(int x, int lx, int rx, int l, int r) {
if (lx>=r || rx<=l) return neutral;
if (lx>=l && rx<=r) return tree[x];
int mid=(lx+rx)/2;
int a=calc(2*x+1,lx,mid,l,r),
b=calc(2*x+2,mid,rx,l,r);
return combine(a,b);
}
int query(int l, int r) {
if (l>=r) return neutral;
return calc(0,0,size,l,r);
}
pi addquery(int x, int lx, int rx, int l, int r) {
if (lx>=r || rx<=l) return {neutral,0};
if (lx>=l && rx<=r) return addtree[x];
int mid=(lx+rx)/2;
pi a=addquery(2*x+1,lx,mid,l,r),
b=addquery(2*x+2,mid,rx,l,r);
pi k = addcombine(a,b,mid,mid+b.s);
//cout<<lx<<' '<<rx<<":\n";
//cout<<a.f<<' '<<a.s<<'\n';
//cout<<b.f<<' '<<b.s<<'\n';
//cout<<k.f<<' '<<k.s<<'\n';
return k;
}
int addquery(int l, int r) {
pi k = addquery(0,0,size,l,r);
//cout<<k.f<<' '<<k.s<<'\n';
return k.f;
}
void set(int i, int v) {
put(size-1+i,v);
update(0, 0, size, i);
}
void print() {
cout<<"TREE: \n";
int z=0;
while (z<addtree.size()) {
for (int i=z; i<2*z+1; i++) cout<<addtree[i].f<<' ';
cout<<'\n';
z=z*2+1;
}
cout<<'\n';
}
};
void solve() {
int n,k; cin>>n>>k;
vii(a,n);
vector<int> b=a;
segtree st(a,0);
int m; cin>>m;
//st.print();
forn(Q,m) {
int q; cin>>q;
if (q==1) {
vector<int> v(k);
forn(i,k) cin>>v[i];
forn(i,k) {
b[v[i]-1]=a[v[(i+1)%k]-1];
}
forn(i,k) {
st.set(v[i]-1,b[v[i]-1]);
}
forn(i,k) a[v[i]-1]=b[v[i]-1];
//forn(i,n) cout<<a[i]<<' '; cout<<'\n';
} else {
int l,r,m; cin>>l>>r>>m;
int L,R;
int res=0;
if ((r+1-l)%2) {
if (l-1+(r+1-l)/2<l+m-2) {
L=r-m;
} else {
L=l+m-2;
}
R=r-(L+1-l);
} else {
if (l-1+(r+1-l)/2<l+m-2) {
L=r-m;
} else {
L=l+m-2;
}
R=r-(L+1-l);
}
//cout<<"["<<l-1<<","<<L<<") ["<<R<<','<<r<<") ";
res+=st.addquery(l-1,L);
//cout<<" | "<<res<<" | ";
res+=1ll*min(L+2-l,m)*st.query(L,r);
//cout<<" | "<<res<<" | ";
res-=st.addquery(R,r);
//cout<<" | "<<res<<" | ";
cout<<res<<'\n';
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//init_primes();
int t=1;
//cin>>t;
while(t--) solve();
paiu moment
}
Compilation message
Main.cpp: In member function 'void segtree::print()':
Main.cpp:184:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | while (z<addtree.size()) {
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
472 KB |
Output is correct |
| 4 |
Correct |
16 ms |
580 KB |
Output is correct |
| 5 |
Correct |
17 ms |
592 KB |
Output is correct |
| 6 |
Correct |
22 ms |
840 KB |
Output is correct |
| 7 |
Correct |
26 ms |
884 KB |
Output is correct |
| 8 |
Correct |
32 ms |
908 KB |
Output is correct |
| 9 |
Correct |
61 ms |
1356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
2440 KB |
Output is correct |
| 2 |
Correct |
170 ms |
2724 KB |
Output is correct |
| 3 |
Correct |
257 ms |
4592 KB |
Output is correct |
| 4 |
Correct |
521 ms |
8688 KB |
Output is correct |
| 5 |
Correct |
776 ms |
9512 KB |
Output is correct |
| 6 |
Correct |
710 ms |
9408 KB |
Output is correct |
| 7 |
Correct |
749 ms |
9316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
471 ms |
4756 KB |
Output is correct |
| 2 |
Correct |
754 ms |
8772 KB |
Output is correct |
| 3 |
Correct |
1310 ms |
9472 KB |
Output is correct |
| 4 |
Correct |
854 ms |
12296 KB |
Output is correct |
