oj.uz

답안 #582570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582570 2022-06-24T06:06:59 Z temporary_juggernaut Addk (eJOI21_addk) C++14
92 / 100
 238 ms 11956 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 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){
			//SOON
			scanf("%d",&type);
		}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:71:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |    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:73:4: note: in expansion of macro 'printl'
   73 |    printl("________________");
      |    ^~~~~~
Main.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
Main.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d",&x);
      |   ~~~~~^~~~~~~~~
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
Main.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d",&type);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    scanf("%d",&type);
      |    ~~~~~^~~~~~~~~~~~
Main.cpp:67:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |    scanf("%d%d%d",&l,&r,&m);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 7 ms 648 KB Output is correct
5 Correct 7 ms 724 KB Output is correct
6 Correct 9 ms 852 KB Output is correct
7 Correct 13 ms 992 KB Output is correct
8 Correct 13 ms 1108 KB Output is correct
9 Correct 17 ms 1364 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2572 KB Output is correct
2 Correct 57 ms 3668 KB Output is correct
3 Correct 107 ms 4856 KB Output is correct
4 Correct 153 ms 8396 KB Output is correct
5 Correct 238 ms 11956 KB Output is correct
6 Correct 191 ms 11804 KB Output is correct
7 Correct 233 ms 11728 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 5804 KB Output isn't correct
2 Halted 0 ms 0 KB -