oj.uz

Submission #205381

# Submission time Handle Problem Language Result Execution time Memory
205381 2020-02-28T17:58:52 Z TadijaSebez Fire (JOI20_ho_t5) C++11
6 / 100
 348 ms 21240 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=200050;
struct BIT{
	ll sum[N];
	void init(){for(int i=0;i<N;i++)sum[i]=0;}
	BIT(){init();}
	void Set(int i,ll f){for(i++;i<N;i+=i&-i)sum[i]+=f;}
	ll Get(int i){ll ans=0;for(i++;i;i-=i&-i)ans+=sum[i];return ans;}
}SUM,MUL,STK;
int a[N];
vector<pair<int,int>> Qs[N];
int stk[N],top;
ll ans[N];
void AddD(int t,ll f){
	//printf("AddD %i %lld\n",t,f);
	SUM.Set(t,-t*f);
	MUL.Set(t,f);
}
ll Get(int t){
	//printf("t:%i mul:%lld sum:%lld\n",t,MUL.Get(t),SUM.Get(t));
	return (t+1)*MUL.Get(t)+SUM.Get(t);
}
int main(){
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	for(int i=1,t,l,r;i<=q;i++)scanf("%i %i %i",&t,&l,&r),Qs[r].pb({i,t}),Qs[l-1].pb({-i,t});
	for(int i=1;i<=n;i++){
		while(top && a[stk[top]]<=a[i]){
			AddD(i-stk[top],-a[stk[top]]);
			if(top>1)AddD(i-stk[top-1],a[stk[top]]);
			if(top>1)STK.Set(top,-(ll)(stk[top]-stk[top-1])*a[stk[top]]);
			top--;
		}
		AddD(0,a[i]);
		if(top>0)AddD(i-stk[top],-a[i]);
		stk[++top]=i;
		if(top>1)STK.Set(top,(ll)(stk[top]-stk[top-1])*a[stk[top]]);
		for(auto Q:Qs[i]){
			int t=Q.second;
			ll now=Get(t);
			//printf("Get: %lld ",now);
			int hi=top,lo=1,mid,pos=top;
			while(hi>=lo){
				mid=hi+lo>>1;
				if(i-stk[mid]<=t)pos=mid,hi=mid-1;
				else lo=mid+1;
			}
			now-=STK.Get(top)-STK.Get(pos);
			//printf("%lld ",now);
			now-=a[stk[pos]]*(t-(i-stk[pos]));
			int id=abs(Q.first);
			//printf("i:%i t:%i now:%lld\n",i,t,now);
			if(Q.first<0)ans[id]-=now;
			else ans[id]+=now;
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:48:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=hi+lo>>1;
         ~~^~~
ho_t5.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:29:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
ho_t5.cpp:30:71: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,t,l,r;i<=q;i++)scanf("%i %i %i",&t,&l,&r),Qs[r].pb({i,t}),Qs[l-1].pb({-i,t});
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Incorrect 10 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Incorrect 303 ms 21240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Incorrect 348 ms 21112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 19832 KB Output is correct
2 Correct 299 ms 19816 KB Output is correct
3 Correct 311 ms 19992 KB Output is correct
4 Correct 322 ms 19960 KB Output is correct
5 Correct 303 ms 19964 KB Output is correct
6 Correct 304 ms 19704 KB Output is correct
7 Correct 312 ms 19960 KB Output is correct
8 Correct 312 ms 19960 KB Output is correct
9 Correct 325 ms 19896 KB Output is correct
10 Correct 298 ms 19832 KB Output is correct
11 Correct 307 ms 20088 KB Output is correct
12 Correct 312 ms 20088 KB Output is correct
13 Correct 311 ms 19960 KB Output is correct
14 Correct 306 ms 19960 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Incorrect 10 ms 9720 KB Output isn't correct
3 Halted 0 ms 0 KB -