oj.uz

Submission #37132

# Submission time Handle Problem Language Result Execution time Memory
37132 2017-12-21T14:54:35 Z Weak123456 Divide and conquer (IZhO14_divide) C++14
100 / 100
 189 ms 20976 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << ", " << 

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 1e5 + 7;
const long long oo = 1e18 + 7;

int n, g;
long long e[N], gg[N];
map <long long, int> mp;
vector <long long> v;

struct mine{
	int x, gold, energy;
}a[N];

struct BIT{
	long long tree[2 * N];

	inline void Init(){
		for (int i = 1; i < 2 * N; i++)
			tree[i] = oo;
	}

	void Update(int x, long long val){
		for (; x <= g; x += (x & (-x)))
			tree[x] = min(tree[x], val);
	}

	long long Query(int x){
		long long res = oo;
		for (; x > 0; x -= (x & (-x)))
			res = min(res, tree[x]);
		return res;
	}
}BIT;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("divide.in", "r", stdin);
	// freopen("divide.out", "w", stdout);
	read(n);
	for (int i = 1; i <= n; i++){
		read(a[i].x); read(a[i].gold); read(a[i].energy);
		e[i] = e[i - 1] + a[i].energy;
		gg[i] = gg[i - 1] + a[i].gold;
		v.push_back(e[i - 1] - a[i].x);
		v.push_back(e[i] - a[i].x);
	}
	v.push_back(0);
	sort(v.begin(), v.end());
	mp[v[0]] = g = 1;
	for (int i = 1; i < v.size(); i++)
		if (v[i] != v[i - 1])
			mp[v[i]] = ++g;
	BIT.Init();
	long long res = 0;
	for (int i = 1; i <= n; i++)
		res = max(res, (long long)a[i].gold);
	for (int i = 1; i <= n; i++){
		// cout << e[i] - a[i].x << ' ' << e[i - 1] - a[i].x << endl;
		int x = mp[e[i] - a[i].x];
		int pos = mp[e[i - 1] - a[i].x];
		long long cur = BIT.Query(x);
		// db(x _ pos _ cur _ gg[i]);
		res = max(res, gg[i] - cur);
		BIT.Update(pos, gg[i - 1]);
	}
	writeln(res);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++)
                    ^

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7172 KB Output is correct
2 Correct 9 ms 7964 KB Output is correct
3 Correct 13 ms 7964 KB Output is correct
4 Correct 76 ms 13748 KB Output is correct
5 Correct 93 ms 13748 KB Output is correct
6 Correct 179 ms 20976 KB Output is correct
7 Correct 189 ms 20976 KB Output is correct
8 Correct 173 ms 20976 KB Output is correct
9 Correct 189 ms 20976 KB Output is correct
10 Correct 159 ms 20580 KB Output is correct
11 Correct 176 ms 20976 KB Output is correct
12 Correct 176 ms 20976 KB Output is correct