Submission #1032138

#TimeUsernameProblemLanguageResultExecution timeMemory
1032138ten_xdAddk (eJOI21_addk)C++17
0 / 100
59 ms9196 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define rep(a,b) for(int a = 0; a < (b); ++a) #define all(t) t.begin(), t.end() #define pb push_back const int N = 1e5+5, INF = 2e9+54321, base = (1<<17), rozmiar_drzewa = base * 2; const ll INF_L = (ll)2e18+54321; int n,k,q; int A[N]; vector<ll> tree, tree2, tree3; void update(int v, int val) { ll val1 = (ll)val * (v+1), val2 = (ll)val * (n-v); v += base, tree[v] = val1, tree2[v] = val2, tree3[v] = val, v /= 2; while(v > 0) tree[v] = tree[v*2] + tree[v*2+1], tree2[v] = tree2[v*2] + tree2[v*2+1], tree3[v] = tree3[v*2] + tree3[v*2+1], v /= 2; } ll query3(int l, int p) { int la = l, pa = p; l = l + base - 1, p = p + base + 1; ll res = 0; while(l/2 != p/2) { if(l % 2 == 0) res += tree3[l+1]; if(p % 2 == 1) res += tree3[p-1]; l /= 2, p /= 2; } //cout << '\n'; //cout << "LLL: " << la << " PPP: " << pa << " RES: " << res << '\n'; //cout << '\n'; return res; } ll query(int l, int p) { ll res = -(ll)l * query3(l,p); //cout << '\n'; //cout << "LL: " << l << " P: " << p << " RES: " << res << '\n'; l = l + base - 1, p = p + base + 1; while(l/2 != p/2) { if(l % 2 == 0) res += tree[l+1]; if(p % 2 == 1) res += tree[p-1]; l /= 2, p /= 2; } //cout << "L: " << l << " P: " << p << " RES: " << res << '\n'; //cout << '\n'; return res; } ll query2(int l, int p) { ll res = -(ll)(n-p-1) * query3(l,p); //cout << '\n'; //cout << "LL2: " << l << " P: " << p << " RES: " << res << '\n'; l = l + base - 1, p = p + base + 1; while(l/2 != p/2) { if(l % 2 == 0) res += tree2[l+1]; if(p % 2 == 1) res += tree2[p-1]; l /= 2, p /= 2; } //cout << "L2: " << l << " P: " << p << " RES: " << res << '\n'; //cout << '\n'; return res; } void solve() { cin >> n >> k; rep(i,n) cin >> A[i]; tree.assign(rozmiar_drzewa,0), tree2.assign(rozmiar_drzewa,0), tree3.assign(rozmiar_drzewa,0); rep(i,n) update(i,A[i]); cin >> q; while(q--) { int dec; cin >> dec; if(dec == 1) { vector<int> V, H; V.assign(k,-1), H.assign(k,-1); rep(i,k) cin >> V[i], --V[i], H[i] = A[V[i]]; int val = A[V[0]]; for(int i = 0; i < k-1; ++i) A[V[i]] = A[V[i+1]], update(V[i],A[V[i]]); A[V[k-1]] = val, update(V[k-1],A[V[k-1]]); } else { int l,p,m,len; cin >> l >> p >> m; --l, --p, len = p-l+1; if(len >= 2*m-1) { ll wyn = query(l,l+m-2) + query2(p-m+2,p) + query3(l+m-1,p-(m-1)) * (ll)m; cout << wyn << '\n'; } else { int idx = p-m+1, dl = idx-l+1; ll wyn = query(l,idx) + query2(p-idx+1,p); if(idx+1 <= p-idx) wyn += query3(idx+1,p-idx) * (ll)dl; cout << wyn << '\n'; } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T = 1; //cin >> T; while(T--) solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'll query3(int, int)':
Main.cpp:25:6: warning: unused variable 'la' [-Wunused-variable]
   25 |  int la = l, pa = p;
      |      ^~
Main.cpp:25:14: warning: unused variable 'pa' [-Wunused-variable]
   25 |  int la = l, pa = p;
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...