oj.uz

Submission #173607

# Submission time Handle Problem Language Result Execution time Memory
173607 2020-01-04T17:08:01 Z nafis_shifat Divide and conquer (IZhO14_divide) C++14
100 / 100
 281 ms 8824 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5;
ll tree[4*mxn]={};
ll lazy[4*mxn]={};
int query(int node,int b,int e,int l,int r)
{
	if(b>r || e<l)return -1;
	if(b==e)return b;
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;

	lazy[left]+=lazy[node];
    lazy[right]+=lazy[node];
    tree[left]+=lazy[node];
    tree[right]+=lazy[node];
    lazy[node]=0;



	if(tree[right]>=0)return query(right,mid+1,e,l,r);
	return query(left,b,mid,l,r);


    
}
void update(int node, int b,int e,int l,int r,ll v)
{
	if(b>r || e<l)return;


	if(b==e)
	{
		tree[node]+=v;
		return;
	}

	if(b>=l && e<=r)
	{
		tree[node]+=v;
		lazy[node]+=v;
		return;
	}
    int left=node*2;
    int right=node*2+1;

    lazy[left]+=lazy[node];
    lazy[right]+=lazy[node];
    tree[left]+=lazy[node];
    tree[right]+=lazy[node];
    lazy[node]=0;

    


    int mid=b+e>>1;
    update(left,b,mid,l,r,v);
    update(right,mid+1,e,l,r,v);

    tree[node]=max(tree[left],tree[right]);
}


int main()
{

	int n;
	cin>>n;
	ll g[n+1]={};
	ll d[n+1]={};
	int x[n+1]={};
	ll ans=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>g[i]>>d[i];
		ans=max(ans,g[i]);
		g[i]+=g[i-1];
	
	}

	int l=1;
	

	update(1,1,n,n,n,d[n]);

	int lst=x[n];
	for(int i=n-1;i>0;i--)
	{
		update(1,1,n,i+1,n,x[i]-lst);
		update(1,1,n,i,n,d[i]);
		int r=query(1,1,n,i,n);
	
		if(r!=-1)
		   ans=max(ans,g[r]-g[i-1]);
		lst=x[i];
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

divide.cpp: In function 'int query(int, int, int, int, int)':
divide.cpp:12:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
divide.cpp: In function 'void update(int, int, int, int, int, long long int)':
divide.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
divide.cpp: In function 'int main()':
divide.cpp:84:6: warning: unused variable 'l' [-Wunused-variable]
  int l=1;
      ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 13 ms 760 KB Output is correct
12 Correct 15 ms 732 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 760 KB Output is correct
2 Correct 18 ms 1144 KB Output is correct
3 Correct 22 ms 1272 KB Output is correct
4 Correct 114 ms 4044 KB Output is correct
5 Correct 131 ms 4728 KB Output is correct
6 Correct 281 ms 8824 KB Output is correct
7 Correct 210 ms 8056 KB Output is correct
8 Correct 217 ms 8156 KB Output is correct
9 Correct 204 ms 8060 KB Output is correct
10 Correct 209 ms 8056 KB Output is correct
11 Correct 237 ms 8604 KB Output is correct
12 Correct 247 ms 8808 KB Output is correct