제출 #37132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37132		Weak123456	Divide and conquer (IZhO14_divide)	C++14	100 / 100	189 ms	20976 KiB

divide

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52