oj.uz

Submission #68449

# Submission time Handle Problem Language Result Execution time Memory
68449 2018-08-17T07:18:43 Z MrTEK Divide and conquer (IZhO14_divide) C++14
48 / 100
 121 ms 12496 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define cout maltahsin
#define left ind + ind
#define right ind + ind + 1
#define mid (l + r) / 2 
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

#define int long long
 
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9 + 5;
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int SQ = 350;
const int MOD = 998244353;
 
typedef pair <int,int> pii;

vector <pair <long long,int> > v;

int n,x[N],g[N],d[N],seg[N << 2],a[N],b[N];
long long ans,pred[N],preg[N];

void update(int ind,int l,int r,int w,int val) {
	if (l > w || r < w) return;
	if (l == w && r == w) {
		seg[ind] = min(seg[ind],val);
		return;
	}
	update(left,l,mid,w,val);
	update(right,mid + 1,r,w,val);
	seg[ind] = min(seg[left],seg[right]);
}

int get(int ind,int l,int r,int lw,int rw) {
	if (l > rw || r < lw) return INF;
	if (l >= lw && r <= rw) return seg[ind];
	return min(get(left,l,mid,lw,rw),get(right,mid + 1,r,lw,rw));
}


main() {

	scanf("%lld",&n);

	for (int i = 1 ; i <= n ; i++) {
		scanf("%lld %lld %lld",&x[i],&g[i],&d[i]);
		pred[i] = pred[i - 1] + d[i];
		preg[i] = preg[i - 1] + g[i];
		v.pb(mp(pred[i] - x[i],i));
		v.pb(mp(pred[i - 1] - x[i],i));
	}

	sort(v.begin(),v.end());

	for (int i = 0, lst = 0; i < len(v) ; i++) {
		if (i == 0 || v[i - 1].fi != v[i].fi) lst++;
		if (b[v[i].sc]) a[v[i].sc] = lst;
		else b[v[i].sc] = lst;
	}

	for (int i = 0 ; i < (N << 2) ; i++) seg[i] = INF;

	for (int i = 1 ; i <= n ; i++) {
		update(1,1,2 * n,b[i],i);
		int lst = get(1,1,2 * n,1,a[i]);
		if (lst != INF) ans = max(preg[i] - preg[lst - 1],ans);
	}
	printf("%lld\n",ans);

}

Compilation message

divide.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
divide.cpp: In function 'int main()':
divide.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
divide.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x[i],&g[i],&d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4328 KB Output is correct
2 Correct 13 ms 4708 KB Output is correct
3 Correct 15 ms 4708 KB Output is correct
4 Correct 54 ms 8152 KB Output is correct
5 Correct 50 ms 8152 KB Output is correct
6 Correct 121 ms 12368 KB Output is correct
7 Correct 102 ms 12472 KB Output is correct
8 Correct 87 ms 12472 KB Output is correct
9 Correct 89 ms 12496 KB Output is correct
10 Incorrect 107 ms 12496 KB Output isn't correct
11 Halted 0 ms 0 KB -