oj.uz

Submission #914208

# Submission time Handle Problem Language Result Execution time Memory
914208 2024-01-21T11:02:41 Z PieArmy Addk (eJOI21_addk) C++17
100 / 100
 212 ms 12672 KB 
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
typedef long long ll;
#define yem(re) (1ll<<(ll(re)))
#define endl '\n'
#define pb push_back
#define int ll
#define mid ((left+right)/2)
#define L(emanuelLasker,joseRaulCapablanca,anatolyKarpov) for(int emanuelLasker=(joseRaulCapablanca);emanuelLasker<=(anatolyKarpov);emanuelLasker++)
#define R(magnusCarlsen,paulMorphy,bobbyFischer) for(int magnusCarlsen=(paulMorphy);magnusCarlsen>=(bobbyFischer);magnusCarlsen--)
#define cint(vladimirKramnik) int vladimirKramnik;cin>>vladimirKramnik
#define inf (2000000000000000005)
#define sc second
#define fr first
#define Bismillahirrahmanirrahim ios_base::sync_with_stdio(false);cin.tie(NULL);
#define cinarr(mikhailTal) for(auto &garryKasparov:mikhailTal)cin>>garryKasparov;
#define all(mustafaKemalAtaturk) mustafaKemalAtaturk.begin(),mustafaKemalAtaturk.end()
 
vector<int>arr;
 
struct Seg{
    int n;
    vector<int>tree;
    Seg(int N){
        n=N;
        tree.resize(n*4);
    }
    void build(bool coklu=false,int node=1,int left=0,int right=-1){
        if(right==-1)right=n-1;
        if(left==right){
            tree[node]=arr[left];
            if(coklu)tree[node]*=left+1;
            return;
        }
        build(coklu,node*2,left,mid);
        build(coklu,node*2+1,mid+1,right);
        tree[node]=tree[node*2]+tree[node*2+1];
        return;
    }
    void update(int tar,int x,bool coklu=false){
        int node=1,left=0,right=n-1;
        while(left<right){
            tree[node]+=x-arr[tar];
            if(coklu)tree[node]+=(x-arr[tar])*tar;
            node*=2;
            if(tar>mid){left=mid+1;node++;}
            else right=mid;
        }
        tree[node]=x;
        if(coklu)tree[node]*=tar+1;
        return;
    }
    int query(int l,int r,int node=1,int left=0,int right=-1){
        if(right==-1)right=n-1;
        if(l>r)return 0;
        if(l>right||r<left)return 0;
        if(l<=left&&r>=right)return tree[node];
        return query(l,r,node*2,left,mid)+query(l,r,node*2+1,mid+1,right);
    }
};
 
void code(){
	int n,k;cin>>n>>k;
    arr.resize(n);cin>>arr;
    Seg B(n);
    Seg C(n);
    B.build();
    C.build(true);
    int q;cin>>q;
    while(q--){
        int typ;cin>>typ;
        if(typ==1){
            int up[k];cinarr(up);
            for(int &x:up)x--;
            for(int i=0;i<k-1;i++){
                B.update(up[i],arr[up[i+1]]);
                C.update(up[i],arr[up[i+1]],true);
            }
            B.update(up[k-1],arr[up[0]]);
            C.update(up[k-1],arr[up[0]],true);
            int bas=arr[up[0]];
            for(int i=0;i<k-1;i++)
                arr[up[i]]=arr[up[i+1]];
            arr[up[k-1]]=bas;
        }
        else{
            int l,r,m;cin>>l>>r>>m;
            l--;r--;
            if(r-l+3>=m*2){
                int ans=B.query(l+m-1,r-m+1)*m;
                if(m==1){cout<<ans<<endl;continue;}
                ans+=C.query(l,l+m-2)-(B.query(l,l+m-2)*l);
                ans+=(B.query(r-m+2,r)*(r+2))-C.query(r-m+2,r);
                cout<<ans<<endl;
            }
            else{
                int ans=B.query(r-m+1,l+m-1)*(r-l+2-m);
                if(m==1||m==r-l+1){cout<<ans<<endl;continue;}
                ans+=C.query(l,r-m)-(B.query(l,r-m)*l);
                ans+=(B.query(l+m,r)*(r+2))-C.query(l+m,r);
                cout<<ans<<endl;
            }
        }
    }
}
 
int32_t main(){
    Bismillahirrahmanirrahim
	int t=1;
    bool usaco=0;
    if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:116:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |               ~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:116:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 976 KB Output is correct
7 Correct 8 ms 1112 KB Output is correct
8 Correct 9 ms 1116 KB Output is correct
9 Correct 14 ms 1368 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2396 KB Output is correct
2 Correct 43 ms 3584 KB Output is correct
3 Correct 64 ms 4944 KB Output is correct
4 Correct 105 ms 7944 KB Output is correct
5 Correct 161 ms 11348 KB Output is correct
6 Correct 142 ms 11108 KB Output is correct
7 Correct 152 ms 11080 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 6224 KB Output is correct
2 Correct 134 ms 9420 KB Output is correct
3 Correct 212 ms 12672 KB Output is correct
4 Correct 163 ms 11604 KB Output is correct