oj.uz

Submission #68440

# Submission time Handle Problem Language Result Execution time Memory
68440 2018-08-17T07:08:33 Z hamzqq9 Divide and conquer (IZhO14_divide) C++14
100 / 100
 132 ms 13024 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 10000000000000000
#define MOD 1000000007
#define N 200005
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;

ll S[N*4],preE[N],preG[N],ans;
int n,x,g,d,coord[N],tut[2][N];
vector< pair<ll, ii > > v;

void up(int node,int bas,int son,int x,ll val) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		umax(S[node],val);

		return ;

	}

	up(node*2,bas,orta,x,val);
	up(node*2+1,orta+1,son,x,val);

	S[node]=max(S[node*2],S[node*2+1]);

}

ll get(int node,int bas,int son,int x,int y) {

	if(bas>y || son<x) return -inf;

	if(bas>=x && son<=y) return S[node];

	return max(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y)); 

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%d %d %d",&x,&g,&d);

		preE[i]=preE[i-1]+d;
		preG[i]=preG[i-1]+g;

		coord[i]=x;

	}	

	for(int i=1;i<=n;i++) {

		v.pb({preE[i]-coord[i],{i,1}});
		v.pb({preE[i-1]-coord[i],{i,0}});

	}

	sort(all(v));

	int cnt=0;

	for(int i=0;i<sz(v);i++) {

		++cnt;

		tut[v[i].nd.nd][v[i].nd.st]=cnt;

		while(i+1<sz(v) && v[i+1].st==v[i].st) {

			i++;
			tut[v[i].nd.nd][v[i].nd.st]=cnt;

		}

	}

	for(int i=0;i<N*4;i++) S[i]=-inf;

	for(int i=1;i<=n;i++) {

		up(1,1,cnt,tut[0][i],-preG[i-1]);

		umax(ans,get(1,1,cnt,1,tut[1][i])+preG[i]);

	}

	printf("%lld\n",ans);

}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&g,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7288 KB Output is correct
2 Correct 16 ms 7536 KB Output is correct
3 Correct 16 ms 7536 KB Output is correct
4 Correct 55 ms 9960 KB Output is correct
5 Correct 90 ms 9964 KB Output is correct
6 Correct 106 ms 13024 KB Output is correct
7 Correct 88 ms 13024 KB Output is correct
8 Correct 111 ms 13024 KB Output is correct
9 Correct 103 ms 13024 KB Output is correct
10 Correct 105 ms 13024 KB Output is correct
11 Correct 122 ms 13024 KB Output is correct
12 Correct 132 ms 13024 KB Output is correct