oj.uz

답안 #31119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31119 2017-08-10T04:00:19 Z trath Foehn Phenomena (JOI17_foehn_phenomena) C++
30 / 100
 43 ms 24676 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long int
#define ieps 200010
#define eps (int) 1e9
#define pii pair<int,int>

 ll read_int(){
	char r;
	bool start=false,neg=false;
	 ll ret=0;
	while(true){
		r=getchar();
		if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
			continue;
		}
		if((r-'0'<0 || r-'0'>9) && r!='-' && start){
			break;
		}
		if(start)ret*=10;
		start=true;
		if(r=='-')neg=true;
		else ret+=r-'0';
	}
	if(!neg)
		return ret;
	else
		return -ret;
}


		

struct node{
	ll leftmost, rightmost, sumup , sumdown;
	void clv(){
		leftmost = rightmost = sumup = sumdown = 0;
	}
};
int a , b , val;
int n , q ,   v[200100] ;
ll s , t;
ll lazy[560000];
node st[560000];

void propagate(int curr){
	if(lazy[curr]){
		st[curr].leftmost += lazy[curr];
		st[curr].rightmost += lazy[curr];
		lazy[2*curr] += lazy[curr];
		lazy[2*curr + 1] += lazy[curr];
		lazy[curr] = 0;
	}
}

node mixnode(node left, node right){
	node x;
	x.clv();
	ll toadd = 0 , tosubtract = 0;
	if(left.rightmost >= right.leftmost){
		toadd += t*(left.rightmost - right.leftmost);
	}
	else if(left.rightmost < right.leftmost){
		tosubtract += s*(right.leftmost - left.rightmost);
	}
	x.leftmost = left.leftmost;
	x.rightmost = right.rightmost;
	x.sumup = left.sumup + right.sumup + toadd;
	x.sumdown = left.sumdown + right.sumdown + tosubtract;
	//cout<<x.sumup<<" "<<x.sumdown<<endl;
	return x;
}

void build(int l = 0 , int r = n- 1 , int curr = 1){
	if(l == r){
		st[curr].clv();
		st[curr].rightmost = st[curr].leftmost  = v[l];
		return;
	}
	build(l , (l+r)/2 , 2*curr);
	build((l+r)/2 + 1 , r, 2*curr + 1);
	st[curr] = mixnode(st[2*curr] , st[2*curr + 1]);
	return;
}

void update(int x , int y , int l = 0 , int r = n- 1 , int curr = 1){
	propagate(curr);
	if(l == x && r == y){
		lazy[curr]+=val;
		propagate(curr);
		return;
	}
	ll mid = (l+r)/2;
	if(y <= mid){
		update(x , y, l , mid , 2*curr);
	}
	else if(x > mid){
		update(x ,y, mid + 1 ,r , 2*curr + 1);
	}
	else{
		update(x , mid , l , mid , 2*curr);
		update(mid + 1 , y , mid + 1 , r , 2*curr + 1);
	}
	propagate(2*curr);
	propagate(2*curr + 1);
	st[curr] = mixnode(st[2*curr] , st[2*curr + 1]);
	return;
}




int main(){
	scanf("%d %d %lld %lld", &n, &q, &s, &t);
	n = n+1;
	for(int i = 0;i<n;i++) scanf("%d", &(v[i]));;
	build();
	for(int i = 0;i<q;i++){
		scanf("%d%d%d", &a, &b, &val);
		update(a , b);
		ll p = st[1].sumup;
		p-=st[1].sumdown;
		printf("%lld\n",p);
	}
	return 0;
}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:118:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld %lld", &n, &q, &s, &t);
                                          ^
foehn_phenomena.cpp:120:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0;i<n;i++) scanf("%d", &(v[i]));;
                                             ^
foehn_phenomena.cpp:123:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &val);
                                ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 24676 KB Output is correct
2 Correct 3 ms 24676 KB Output is correct
3 Correct 3 ms 24676 KB Output is correct
4 Correct 0 ms 24676 KB Output is correct
5 Correct 0 ms 24676 KB Output is correct
6 Correct 3 ms 24676 KB Output is correct
7 Correct 3 ms 24676 KB Output is correct
8 Correct 0 ms 24676 KB Output is correct
9 Correct 3 ms 24676 KB Output is correct
10 Correct 3 ms 24676 KB Output is correct
11 Correct 3 ms 24676 KB Output is correct
12 Correct 3 ms 24676 KB Output is correct
13 Correct 0 ms 24676 KB Output is correct
14 Correct 0 ms 24676 KB Output is correct
15 Correct 0 ms 24676 KB Output is correct
16 Correct 3 ms 24676 KB Output is correct
17 Correct 0 ms 24676 KB Output is correct
18 Correct 0 ms 24676 KB Output is correct
19 Correct 0 ms 24676 KB Output is correct
20 Correct 0 ms 24676 KB Output is correct
21 Correct 0 ms 24676 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 24676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 24676 KB Output is correct
2 Correct 3 ms 24676 KB Output is correct
3 Correct 3 ms 24676 KB Output is correct
4 Correct 0 ms 24676 KB Output is correct
5 Correct 0 ms 24676 KB Output is correct
6 Correct 3 ms 24676 KB Output is correct
7 Correct 3 ms 24676 KB Output is correct
8 Correct 0 ms 24676 KB Output is correct
9 Correct 3 ms 24676 KB Output is correct
10 Correct 3 ms 24676 KB Output is correct
11 Correct 3 ms 24676 KB Output is correct
12 Correct 3 ms 24676 KB Output is correct
13 Correct 0 ms 24676 KB Output is correct
14 Correct 0 ms 24676 KB Output is correct
15 Correct 0 ms 24676 KB Output is correct
16 Correct 3 ms 24676 KB Output is correct
17 Correct 0 ms 24676 KB Output is correct
18 Correct 0 ms 24676 KB Output is correct
19 Correct 0 ms 24676 KB Output is correct
20 Correct 0 ms 24676 KB Output is correct
21 Correct 0 ms 24676 KB Output is correct
22 Runtime error 43 ms 24676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -