Submission #582577

# Submission time Handle Problem Language Result Execution time Memory
582577 2022-06-24T06:13:30 Z temporary_juggernaut Addk (eJOI21_addk) C++14
100 / 100
401 ms 11948 KB
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
struct SegmentTree{
	vector<ll>tree;
	void build(int n){
		tree.assign(n<<2|3,0);
	}
	ll get(int v,int l,int r,int ql,int qr){
		if(qr<l||r<ql)return 0ll;
		if(ql<=l&&r<=qr)return tree[v];
		int mid=(l+r)>>1;
		return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid+1,r,ql,qr);
	}
	void update(int v,int l,int r,int pos,ll val){
		if(l==r){
			tree[v]=val;
			return;
		}
		int mid=(l+r)>>1;
		if(pos>mid)update(v<<1|1,mid+1,r,pos,val);
		else update(v<<1,l,mid,pos,val);
		tree[v]=tree[v<<1]+tree[v<<1|1];
	}
}tree[3];
ll a[100005];
int b[100005];
int main(){
	int n,k,q;
	scanf("%d%d",&n,&k);
	tree[0].build(n);
	tree[1].build(n);
	tree[2].build(n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[i]=x;
		tree[0].update(1,1,n,i,a[i]);
		tree[1].update(1,1,n,i,a[i]*i);
		tree[2].update(1,1,n,i,a[i]*(n-i+1));
	}
	scanf("%d",&q);
	while(q--){
		int type;
		scanf("%d",&type);
		if(type&1){
			for(int i=0;i<k;i++)scanf("%d",&b[i]);
			ll temp=a[b[0]];
			for(int i=1;i<k;i++){
				tree[0].update(1,1,n,b[i-1],a[b[i]]);
				tree[1].update(1,1,n,b[i-1],a[b[i]]*b[i-1]);
				tree[2].update(1,1,n,b[i-1],a[b[i]]*(n-b[i-1]+1));
				a[b[i-1]]=a[b[i]];
			}			
			tree[0].update(1,1,n,b[k-1],temp);
			tree[1].update(1,1,n,b[k-1],temp*b[k-1]);
			tree[2].update(1,1,n,b[k-1],temp*(n-b[k-1]+1));
			a[b[k-1]]=temp;
		}else{
			int l,r,m;
			ll ans=0;
			scanf("%d%d%d",&l,&r,&m);
			if(2*m>r-l+1)m=r-l+2-m;
			ans+=tree[1].get(1,1,n,l,l+m-1)-tree[0].get(1,1,n,l,l+m-1)*1ll*(l-1);
			ans+=tree[2].get(1,1,n,r-m+1,r)-tree[0].get(1,1,n,r-m+1,r)*1ll*(n-r);
			if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
			else ans+=tree[0].get(1,1,n,l+m,r-m)*(1ll*m);
			printl("________________");
			printf("%lld\n",ans);
		}
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:82:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |    if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
      |                             ~^~
Main.cpp:18:29: warning: statement has no effect [-Wunused-value]
   18 |     #define printl(args...) 0
      |                             ^
Main.cpp:84:4: note: in expansion of macro 'printl'
   84 |    printl("________________");
      |    ^~~~~~
Main.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
Main.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
Main.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
Main.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d",&type);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:63:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    for(int i=0;i<k;i++)scanf("%d",&b[i]);
      |                        ~~~~~^~~~~~~~~~~~
Main.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |    scanf("%d%d%d",&l,&r,&m);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 7 ms 764 KB Output is correct
6 Correct 8 ms 872 KB Output is correct
7 Correct 10 ms 980 KB Output is correct
8 Correct 12 ms 1108 KB Output is correct
9 Correct 17 ms 1396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 40 ms 2584 KB Output is correct
2 Correct 59 ms 3708 KB Output is correct
3 Correct 82 ms 4840 KB Output is correct
4 Correct 147 ms 8420 KB Output is correct
5 Correct 215 ms 11948 KB Output is correct
6 Correct 234 ms 11752 KB Output is correct
7 Correct 194 ms 11752 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 158 ms 5852 KB Output is correct
2 Correct 204 ms 9552 KB Output is correct
3 Correct 401 ms 11212 KB Output is correct
4 Correct 240 ms 11940 KB Output is correct