| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684180 |
2023-01-20T15:26:57 Z |
Victor |
Addk (eJOI21_addk) |
C++17 |
|
386 ms |
18440 KB |
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int arr[1'000'005],n,k;
struct Node {
int lo,hi;
ll sum,inc_sum,dec_sum;
Node *l,*r;
Node(int L,int R) : lo(L),hi(R) {
if(lo+1==hi) sum=inc_sum=dec_sum=arr[lo];
else {
int mid=(lo+hi)/2;
l=new Node(lo,mid);
r=new Node(mid,hi);
merge();
}
}
pair<ll,pll> query(int L,int R,int type) {
if(hi<=L||R<=lo) return {0,{0,0}};
if(L<=lo&&hi<=R) {
if(type==0) return {sum,{hi-lo,sum}};
if(type==1) return {inc_sum,{hi-lo,sum}};
if(type==2) return {dec_sum,{hi-lo,sum}};
}
int lvals,rvals;
ll lsum,rsum,lsum1,rsum1;
auto a=l->query(L,R,type);
auto b=r->query(L,R,type);
lsum1=a.first;
rsum1=b.first;
tie(lvals,lsum)=a.second;
tie(rvals,rsum)=b.second;
/*if(type==1) {
cout<<"lo = "<<lo<<" hi = "<<hi<<endl;
cout<<"lsum = "<<lsum1<<" rsum = "<<rsum1<<" lvals = "<<lvals<<" rvals = "<<rvals<<endl;
cout<<"sum = "<<lsum+rsum<<endl<<endl;
}*/
if(type==0) return {lsum1+rsum1,{lvals+rvals,lsum+rsum}};
if(type==1) return {lsum1+rsum1+rsum*lvals,{lvals+rvals,lsum+rsum}};
if(type==2) return {lsum1+rsum1+lsum*rvals,{lvals+rvals,lsum+rsum}};
}
void set(int x,int pos) {
if(hi<=pos||pos<lo) return;
if(lo+1==hi) {
sum=inc_sum=dec_sum=x;
//cout<<"x = "<<x<<" pos = "<<pos<<" lo = "<<lo<<" hi = "<<hi<<endl;
return;
}
l->set(x,pos);
r->set(x,pos);
merge();
//cout<<"lo = "<<lo<<" hi = "<<hi<<" sum = "<<sum<<" inc_sum = "<<inc_sum<<" dec_sum = "<<dec_sum<<endl;
}
void merge() {
int mid=(lo+hi)/2;
int lvals=mid-lo,rvals=hi-mid;
sum=l->sum+r->sum;
inc_sum=l->inc_sum+r->inc_sum+r->sum*lvals;
dec_sum=l->dec_sum+r->dec_sum+l->sum*rvals;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int indexes[10];
cin>>n>>k;
rep(i,0,n) cin>>arr[i];
Node segtree(0,n);
int q;
cin>>q;
while(q--) {
int type;
cin>>type;
if(type==1) {
rep(i,0,k) cin>>indexes[i],--indexes[i];
rep(i,0,k-1) swap(arr[indexes[i]],arr[indexes[i+1]]);
rep(i,0,k) segtree.set(arr[indexes[i]],indexes[i]);//cout<<"index = "<<indexes[i]<<" val = "<<arr[indexes[i]]<<endl;
//rep(i,0,n) cout<<arr[i]<<' ';
//cout<<endl<<endl;
} else {
int lo,hi,m;
cin>>lo>>hi>>m;
--lo;
int mx=min(hi-lo-m+1,m);
//cout<<"mx = "<<mx<<' '<<hi-lo-m<<endl;
//segtree.query(lo,lo+mx-1,1);
//cout<<segtree.query(lo,lo+mx-1,1).first<<' '<<segtree.query(lo,lo+mx-1,1).second.first<<endl;
//cout<<segtree.query(lo+mx-1,hi-mx+1,0).first<<' '<<segtree.query(lo+mx-1,hi-mx+1,0).second.first<<endl;
//cout<<segtree.query(hi-mx+1,hi,2).first<<' '<<segtree.query(hi-mx+1,hi,2).second.first<<endl;
//
cout<<segtree.query(lo,lo+mx-1,1).first+segtree.query(lo+mx-1,hi-mx+1,0).first*mx+segtree.query(hi-mx+1,hi,2).first<<'\n';
//break;
}
}
return 0;
}
Compilation message
Main.cpp: In member function 'std::pair<long long int, std::pair<long long int, long long int> > Node::query(int, int, int)':
Main.cpp:78:5: warning: control reaches end of non-void function [-Wreturn-type]
78 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
4 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
7 ms |
980 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1280 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1416 KB |
Output is correct |
| 9 |
Correct |
14 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
3620 KB |
Output is correct |
| 2 |
Correct |
54 ms |
5324 KB |
Output is correct |
| 3 |
Correct |
86 ms |
7024 KB |
Output is correct |
| 4 |
Correct |
167 ms |
12108 KB |
Output is correct |
| 5 |
Correct |
241 ms |
17176 KB |
Output is correct |
| 6 |
Correct |
251 ms |
16908 KB |
Output is correct |
| 7 |
Correct |
222 ms |
16868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
9144 KB |
Output is correct |
| 2 |
Correct |
249 ms |
14312 KB |
Output is correct |
| 3 |
Correct |
386 ms |
18440 KB |
Output is correct |
| 4 |
Correct |
282 ms |
17432 KB |
Output is correct |
