제출 #120700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120700		onjo0127	Cake 3 (JOI19_cake3)	C++11	100 / 100	1117 ms	156464 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
 
struct Node {
	int c; long long s;
	int lc, rc;
};
 
const long long INF = 1LL * 1e18;
const Node emp = {0, 0, -1, -1};
 
struct PST {
	vector<int> root;
	vector<Node> T;
	void init(int idx, int s, int e) {
		T[idx] = emp;
		if(s == e) return;
		T[idx].lc = idx*2;
		T[idx].rc = idx*2+1;
		int m = s+e >> 1;
		init(idx*2, s, m);
		init(idx*2+1, m+1, e);
	}
	long long get(int pid, int nid, int s, int e, int k) {
		//printf("pseg get: pid: %d, nid: %d, s: %d, e: %d, k: %d\n", pid, nid, s, e, k);
		int cnt = T[nid].c - T[pid].c;
		if(cnt == k) return T[nid].s - T[pid].s;
		if(cnt < k) return -INF;
		int plc = T[pid].lc, nlc = T[nid].lc, prc = T[pid].rc, nrc = T[nid].rc, m = s+e >> 1;
		int rcnt = T[nrc].c - T[prc].c;
		if(rcnt >= k) return get(prc, nrc, m+1, e, k);
		return T[nrc].s - T[prc].s + get(plc, nlc, s, m, k - rcnt);
	}
	long long ksum(int l, int r, int s, int e, int k) {
		return get(root[l], root[r], s, e, k);
	}
	void upd(int pid, int nid, int s, int e, int p, int v) {
		//printf("pseg upd: pid: %d nid: %d s: %d e: %d p: %d v: %d\n", pid, nid, s, e, p, v);
		if(s == e) {
			++T[nid].c;
			T[nid].s += v;
			return;
		}
		int m = s+e >> 1;
		if(p <= m) {
			T[nid].lc = T.size();
			T.push_back(T[T[pid].lc]);
			upd(T[pid].lc, T[nid].lc, s, m, p, v);
			T[nid].rc = T[pid].rc;
		}
		else {
			T[nid].lc = T[pid].lc;
			T[nid].rc = T.size();
			T.push_back(T[T[pid].rc]);
			upd(T[pid].rc, T[nid].rc, m+1, e, p, v);
		}
		int LC = T[nid].lc, RC = T[nid].rc;
		T[nid].c = T[LC].c + T[RC].c;
		T[nid].s = T[LC].s + T[RC].s;
	}
	void update(int s, int e, int p, int v) {
		int pid = root.back(), nid = T.size();
		root.push_back(nid);
		T.push_back(T[pid]);
		upd(pid, nid, s, e, p, v);
	}
	void initalization(int sz) {
		root.push_back(1);
		T.resize(4*sz);
		init(1, 1, sz);
	}
};
 
PST pseg;
long long ans = -INF;
int N, M, V[200009], C[200009], ord[200009];
vector<int> S = {0};
 
void dnc(int s, int e, int l, int r) {
	if(e < s || r < l) return;
	int m = s+e >> 1;
	int st = max(m + M - 1, l), en = r, mxi = r;
	int L = S[m];
	long long mx = -INF;
	for(int i=st; i<=en; i++) {
		int R = S[i];
		long long tmp = - 2LL * (C[R] - C[L]) + V[L] + V[R] + pseg.ksum(m, i-1, 1, N, M-2);
		if(mx <= tmp) mxi = i, mx = tmp;
		ans = max(ans, tmp);
	}
	dnc(s, m-1, l, mxi);
	dnc(m+1, e, mxi, r);
}
 
int main() {
	vector<pii> VS;
	scanf("%d%d",&N,&M);
	for(int i=1; i<=N; i++) {
		scanf("%d%d",&V[i],&C[i]);
		VS.push_back({V[i], i});
		S.push_back(i);
	} C[0] = -1e9;
	sort(S.begin(), S.end(), [&](int P, int Q) {return C[P] < C[Q];});
	sort(VS.begin(), VS.end());
	for(int i=1; i<=N; i++) ord[VS[i-1].second] = i;
	pseg.initalization(N);
	for(int i=1; i<=N; i++) {
		int it = S[i];
		pseg.update(1, N, ord[it], V[it]);
	}
	dnc(1, N, 1, N);
	printf("%lld", ans);
	return 0;
}

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

cake3.cpp: In member function 'void PST::init(int, int, int)':
cake3.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
cake3.cpp: In member function 'long long int PST::get(int, int, int, int, int)':
cake3.cpp:30:80: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int plc = T[pid].lc, nlc = T[nid].lc, prc = T[pid].rc, nrc = T[nid].rc, m = s+e >> 1;
                                                                               ~^~
cake3.cpp: In member function 'void PST::upd(int, int, int, int, int, int)':
cake3.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
cake3.cpp: In function 'int main()':
cake3.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~
cake3.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&V[i],&C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76