Submission #1176020

#TimeUsernameProblemLanguageResultExecution timeMemory
1176020NonozeAddk (eJOI21_addk)C++20
92 / 100
229 ms11928 KiB
/* * Author: Nonoze * Created: Saturday 29/03/2025 */ #include <bits/stdc++.h> using namespace std; #ifndef DEBUG #define dbg(...) #endif // #define cout cerr << "OUT: " #define endl '\n' #define endlfl '\n' << flush #define quit(x) return (void)(cout << x << endl) template<typename T> void read(T& x) { cin >> x;} template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);} template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); } template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); } template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); } template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); } template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; } #define sz(x) (int)(x.size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define make_unique(v) sort(all(v)), v.erase(unique(all(v)), (v).end()) #define pb push_back #define mp(a, b) make_pair(a, b) #define fi first #define se second #define cmin(a, b) a = min(a, b) #define cmax(a, b) a = max(a, b) #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define QYES quit("YES") #define QNO quit("NO") #define int long long #define double long double const int inf = numeric_limits<int>::max() / 4; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9+7, LOG=20; void solve(); signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1; // cin >> tt; while(tt--) solve(); return 0; } struct segtree { vector<int> tl, tr, sm; int n; segtree(int _n, vector<int>& a) { n=_n; tl.resize(4*n), tr.resize(4*n), sm.resize(4*n); build(0, 0, n-1, a); } void build(int node, int l, int r, vector<int>& a) { if (l==r) { tl[node]=tr[node]=sm[node]=a[l]; return; } int mid=(l+r)/2; build(node*2+1, l, mid, a); build(node*2+2, mid+1, r, a); sm[node]=sm[node*2+1] + sm[node*2+2]; tl[node]=tl[node*2+1] + tl[node*2+2] + sm[node*2+2]*(mid-l+1); tr[node]=tr[node*2+2] + tr[node*2+1] + sm[node*2+1]*(r-mid); } void update(int node, int l, int r, int point, int val) { if (l>point || r<point) return; if (l==r) { tl[node]=tr[node]=sm[node]=val; return; } int mid=(l+r)/2; update(node*2+1, l, mid, point, val); update(node*2+2, mid+1, r, point, val); sm[node]=sm[node*2+1] + sm[node*2+2]; tl[node]=tl[node*2+1] + tl[node*2+2] + sm[node*2+2]*(mid-l+1); tr[node]=tr[node*2+2] + tr[node*2+1] + sm[node*2+1]*(r-mid); } vector<int> query(int node, int l, int r, int ql, int qr) { if (l>=ql && r<=qr) return {tl[node], tr[node], sm[node]}; int mid=(l+r)/2; if (qr<=mid) return query(node*2+1, l, mid, ql, qr); if (ql>mid) return query(node*2+2, mid+1, r, ql, qr); auto left=query(node*2+1, l, mid, ql, min(mid, qr)); auto right=query(node*2+2, mid+1, r, max(mid+1, ql), qr); return { left[0] + right[0] + right[2]*(mid-ql+1), right[1] + left[1] + left[2]*(qr-mid), left[2] + right[2] }; } }; int n, k, m, q; vector<int> a; void solve() { read(n, k); a.clear(), a.resize(n); read(a); segtree st(n, a); read(q); while (q--) { int t; read(t); if (t==1) { vector<int> is(k); read(is); for (auto &u: is) u--; vector<int> b(k); for (int i=0; i<k; i++) b[i]=a[is[i]]; for (int i=0; i<k; i++) { st.update(0, 0, n-1, is[i], b[(i+1)%k]); } } else { int l, r; read(l, r, m); l--, r--; int ans=0; int nb=min(m-1, (r-l+1)-m+1), mul=min(m, (r-l+1)-m+1); if (nb) ans+=st.query(0, 0, n-1, l, l+nb-1)[0]; if (l+nb<=r-nb) { ans+=st.query(0, 0, n-1, l+nb, r-nb)[2]*mul; } if (nb) ans+=st.query(0, 0, n-1, r-nb+1, r)[1]; cout << ans << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...