oj.uz

Submission #636413

# Submission time Handle Problem Language Result Execution time Memory
636413 2022-08-29T08:35:23 Z deme_bz Addk (eJOI21_addk) C++14
100 / 100
 312 ms 5212 KB 
/**
 *    author:  demetre_bzekalava
**/

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define eb emplace_back
#define sz(x) (int)x.size()
using namespace std;
const int N=2e5+1;
int n,k,q;
ll tree[N][2],a[N];
 
void upd(ll val, int pos, int k){
    while(pos < N){
        tree[pos][k] += val;
        pos += (pos & -pos);
    }
}
 
ll get(int pos, int k){
    ll res = 0;
    while(pos > 0){
        res += tree[pos][k];
        pos -= (pos & -pos);
    }
 
    return res;
}
 
ll range_query(int l, int r, int k){
    return get(r, k) - get(l-1, k);
}

void test_case(){
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		upd(a[i],i,0);
		upd((ll)(a[i]*i),i,1);
	}
	cin >> q;
	while(q--){
		int t;
		cin >> t;
		if(t==1){
			int ind[k];
			for(int i=0;i<k;i++){
				cin >> ind[i];
			}
			
			int f=a[ind[0]];
			for(int i=0;i<k;i++){
				int c=ind[i];
				int b=ind[(i+1)%k];
				ll valc=a[c];
				ll valb=a[b];
				if(i<k-1){
					a[c]=a[b];
				}
				else{
					valb=f;
					a[c]=f;
				}
				upd(valb-valc,c,0);
				upd((valb-valc)*c,c,1);
			}
		}
		else{
			int l,r,m;
			cin >> l >> r >> m;
            int mid=(l+r)/2;
            int l1=0;
            int r1=0;
            if((r-l+1)<m*2-1){
                m=(r-l+1)-m+1;
            }
            l1=l+m-1;
            r1=r-m+1;
            ll res1=range_query(l, l1-1, 1)-(l-1)*range_query(l, l1-1, 0);
            ll res2=range_query(l1, r1, 0)*m;
            ll res3=range_query(r1+1, r, 1)-(r1)*range_query(r1+1, r, 0);
            res3=(r-r1+1)*range_query(r1+1, r, 0)-res3;
            cout << res1+res2+res3 << endl;
		}
	}
}

int main(){

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message

Main.cpp:5:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    5 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
Main.cpp: In function 'void test_case()':
Main.cpp:77:17: warning: unused variable 'mid' [-Wunused-variable]
   77 |             int mid=(l+r)/2;
      |                 ^~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 10 ms 468 KB Output is correct
6 Correct 13 ms 624 KB Output is correct
7 Correct 15 ms 680 KB Output is correct
8 Correct 18 ms 724 KB Output is correct
9 Correct 25 ms 876 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1484 KB Output is correct
2 Correct 97 ms 2220 KB Output is correct
3 Correct 115 ms 2636 KB Output is correct
4 Correct 187 ms 3916 KB Output is correct
5 Correct 255 ms 5084 KB Output is correct
6 Correct 244 ms 4908 KB Output is correct
7 Correct 228 ms 4848 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 2636 KB Output is correct
2 Correct 213 ms 4092 KB Output is correct
3 Correct 304 ms 4268 KB Output is correct
4 Correct 312 ms 5212 KB Output is correct