oj.uz

Submission #29369

# Submission time Handle Problem Language Result Execution time Memory
29369 2017-07-19T07:45:15 Z PrOAhMeT Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 296 ms 7488 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=200005;
int n,q,a[MAXN];
LL fen[MAXN],s,tt;

struct fenwick_tree {
	
	LL fen[MAXN];

	void upd(int x,LL y) {

		++x;
		for(;x<MAXN;x+=x&-x)
			fen[x]+=y;

	}

	LL get(int x) {

		++x;
		LL ret=0;
		for(;x;x-=x&-x)
			ret+=fen[x];
		return ret;

	}

} h,t;

int main() {

	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	cin>>n>>q>>s>>tt;
	LL temp=0;
	for(int i=0;i<=n;++i) {
		cin>>a[i];
		if(i>0) {
			if(a[i]>a[i-1]) {
				t.upd(i,-s*(a[i]-a[i-1]));
			}
			else {
				t.upd(i,tt*(a[i-1]-a[i]));
			}
		}
		if(i) h.upd(i,a[i]-a[i-1]);
		else h.upd(i,a[i]);
	}
	int l,r,x;
	LL bef,cur,beft,curt,nw;
	for(int i=0;i<q;++i) {
		cin>>l>>r>>x;
		LL oldl,oldr;
		if(l>0)
			oldl=t.get(l)-t.get(l-1);
		if(r<n)
			oldr=t.get(r+1)-t.get(r);
		h.upd(l,x);
		h.upd(r+1,-x);
		if(l>0) {
			bef=h.get(l-1);
			cur=h.get(l);
			if(bef>cur) {
				t.upd(l,tt*(bef-cur)-oldl);
			}
			else t.upd(l,-s*(cur-bef)-oldl);
		}
		if(r<n) {
			bef=h.get(r);
			cur=h.get(r+1);
			if(cur<bef) {
				t.upd(r+1,tt*(bef-cur)-oldr);
			}
			else t.upd(r+1,-s*(cur-bef)-oldr);
		}
		//cout<<"update "<<i+1<<endl;
		//for(int j=0;j<=n;++j)
			//cout<<j<<" "<<t.get(j)<<" "<<h.get(j)<<endl;
		cout<<t.get(n)<< endl;
	}

}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:44:5: warning: unused variable 'temp' [-Wunused-variable]
  LL temp=0;
     ^
foehn_phenomena.cpp:59:13: warning: unused variable 'beft' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
             ^
foehn_phenomena.cpp:59:18: warning: unused variable 'curt' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
                  ^
foehn_phenomena.cpp:59:23: warning: unused variable 'nw' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
                       ^
foehn_phenomena.cpp:75:14: warning: 'oldl' may be used uninitialized in this function [-Wmaybe-uninitialized]
    else t.upd(l,-s*(cur-bef)-oldl);
              ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7488 KB Output is correct
2 Correct 6 ms 7488 KB Output is correct
3 Correct 0 ms 7488 KB Output is correct
4 Correct 3 ms 7488 KB Output is correct
5 Correct 9 ms 7488 KB Output is correct
6 Correct 19 ms 7488 KB Output is correct
7 Correct 16 ms 7488 KB Output is correct
8 Correct 29 ms 7488 KB Output is correct
9 Correct 23 ms 7488 KB Output is correct
10 Correct 6 ms 7488 KB Output is correct
11 Correct 9 ms 7488 KB Output is correct
12 Correct 6 ms 7488 KB Output is correct
13 Correct 0 ms 7488 KB Output is correct
14 Correct 6 ms 7488 KB Output is correct
15 Correct 0 ms 7488 KB Output is correct
16 Correct 0 ms 7488 KB Output is correct
17 Correct 3 ms 7488 KB Output is correct
18 Correct 6 ms 7488 KB Output is correct
19 Correct 0 ms 7488 KB Output is correct
20 Correct 0 ms 7488 KB Output is correct
21 Correct 0 ms 7488 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 7488 KB Execution timed out (wall clock limit exceeded)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7488 KB Output is correct
2 Correct 6 ms 7488 KB Output is correct
3 Correct 0 ms 7488 KB Output is correct
4 Correct 3 ms 7488 KB Output is correct
5 Correct 9 ms 7488 KB Output is correct
6 Correct 19 ms 7488 KB Output is correct
7 Correct 16 ms 7488 KB Output is correct
8 Correct 29 ms 7488 KB Output is correct
9 Correct 23 ms 7488 KB Output is correct
10 Correct 6 ms 7488 KB Output is correct
11 Correct 9 ms 7488 KB Output is correct
12 Correct 6 ms 7488 KB Output is correct
13 Correct 0 ms 7488 KB Output is correct
14 Correct 6 ms 7488 KB Output is correct
15 Correct 0 ms 7488 KB Output is correct
16 Correct 0 ms 7488 KB Output is correct
17 Correct 3 ms 7488 KB Output is correct
18 Correct 6 ms 7488 KB Output is correct
19 Correct 0 ms 7488 KB Output is correct
20 Correct 0 ms 7488 KB Output is correct
21 Correct 0 ms 7488 KB Output is correct
22 Runtime error 296 ms 7488 KB Execution timed out (wall clock limit exceeded)
23 Halted 0 ms 0 KB -