oj.uz

Submission #136350

# Submission time Handle Problem Language Result Execution time Memory
136350 2019-07-25T07:30:16 Z dndhk Cake 3 (JOI19_cake3) C++14
100 / 100
 1120 ms 200224 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;

int N, M;
vector<pll> vt;
ll ans = -INFLL;
priority_queue<ll> pq1, pq2;
int sz = 0;

struct PST{
	struct NODE{
		int l=-1, r=-1;
		int cnt=0;
		ll sum=0;
	};
	int SZ;
	vector<NODE> seg;
	int num = 0;
	vector<int> Tree;
	void Init(int x){
		seg.resize(MAX_N*40);
		SZ = x;
		Tree.pb(num++);
		init(Tree[0], 0, SZ-1);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = num++;
		seg[idx].r = num++;
		init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, ll y){
		Tree.pb(update(Tree.back(), 0, SZ-1, x, y));
	}
	int update(int pidx, int s, int e, int x, ll y){
		if(x<s || x>e)	return pidx;
		int idx = num++;
		if(s==e){
			seg[idx].sum = y; seg[idx].cnt = 1;
			return idx;
		}
		int k = update(seg[pidx].l, s, (s+e)/2, x, y); seg[idx].l = k;
		k = update(seg[pidx].r, (s+e)/2+1, e, x, y); seg[idx].r = k;
		seg[idx].sum = seg[seg[idx].l].sum + seg[seg[idx].r].sum;
		seg[idx].cnt = seg[seg[idx].l].cnt + seg[seg[idx].r].cnt;
		return idx;
	}
	ll Calc(int x, int y, int k){
		return calc(Tree[x], Tree[y], 0, SZ-1, k);
	}
	ll calc(int idx1, int idx2, int s, int e, int k){
		//cout<<idx1<<" "<<idx2<<" "<<s<<" "<<e<<" "<<k<<endl;
		//cout<<seg[idx2].cnt<<" "<<seg[idx1].cnt<<endl;
		if(seg[idx2].cnt - seg[idx1].cnt == k){
			return seg[idx2].sum - seg[idx1].sum;
		}
		if(seg[seg[idx2].r].cnt - seg[seg[idx1].r].cnt < k){
			return (seg[seg[idx2].r].sum - seg[seg[idx1].r].sum) + calc(seg[idx1].l, seg[idx2].l, s, (s+e)/2 , k - (seg[seg[idx2].r].cnt - seg[seg[idx1].r].cnt));
		}else{
			return calc(seg[idx1].r, seg[idx2].r, (s+e)/2+1, e, k);
		}
	}
};

PST Pst;

ll csum(int x, int y){
	//cout<<"*"<<x<<" "<<y<<endl;
	return Pst.Calc(x, y+1, M);
}

void calc(int x, int y, int s, int e){
	if(x>y)	return;
	int m = (x+y)/2;
	ll mx = -INFLL, idx = 0;
	for(int i=e; i>=s; i--){
		if(m-i+1<M)	continue;
		ll c = csum(i, m);
		if(mx < c - 2 * (vt[m].first - vt[i].first)){
			mx = c - 2 * (vt[m].first - vt[i].first);
			idx = i;
		}
	}
	ans = max(ans, mx);
	calc(x, m-1, s, idx); calc(m+1, y, idx, e);
}

vector<pll> upd;

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		ll a, b;
		scanf("%lld%lld", &a, &b);
		vt.pb({b, a});
	}
	sort(vt.begin(), vt.end());
	for(int i=0; i<N; i++){
		upd.pb({vt[i].second, i});
	}
	sort(upd.begin(), upd.end());
	Pst.Init(N);
	for(int i=0; i<N; i++){
		upd[i].first = upd[i].second;
		upd[i].second = i;
	}
	sort(upd.begin(), upd.end());
	for(int i=0; i<N; i++){
		Pst.Update(upd[i].second, vt[i].second);
	}
	calc(0, N-1, 0, N-1);
	cout<<ans;
	return 0;
}

Compilation message

cake3.cpp: In function 'int main()':
cake3.cpp:113: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:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 188280 KB Output is correct
2 Correct 155 ms 188192 KB Output is correct
3 Correct 155 ms 188280 KB Output is correct
4 Correct 155 ms 188252 KB Output is correct
5 Correct 160 ms 188460 KB Output is correct
6 Correct 157 ms 188152 KB Output is correct
7 Correct 154 ms 188152 KB Output is correct
8 Correct 155 ms 188344 KB Output is correct
9 Correct 158 ms 188264 KB Output is correct
10 Correct 155 ms 188208 KB Output is correct
11 Correct 155 ms 188280 KB Output is correct
12 Correct 154 ms 188152 KB Output is correct
13 Correct 155 ms 188280 KB Output is correct
14 Correct 158 ms 188220 KB Output is correct
15 Correct 155 ms 188212 KB Output is correct
16 Correct 158 ms 188256 KB Output is correct
17 Correct 154 ms 188196 KB Output is correct
18 Correct 158 ms 188228 KB Output is correct
19 Correct 155 ms 188180 KB Output is correct
20 Correct 163 ms 188320 KB Output is correct
21 Correct 154 ms 188152 KB Output is correct
22 Correct 153 ms 188224 KB Output is correct
23 Correct 154 ms 188280 KB Output is correct
24 Correct 154 ms 188196 KB Output is correct
25 Correct 154 ms 188200 KB Output is correct
26 Correct 156 ms 188216 KB Output is correct
27 Correct 162 ms 188192 KB Output is correct
28 Correct 154 ms 188252 KB Output is correct
29 Correct 156 ms 188244 KB Output is correct
30 Correct 154 ms 188152 KB Output is correct
31 Correct 155 ms 188304 KB Output is correct
32 Correct 154 ms 188280 KB Output is correct
33 Correct 154 ms 188280 KB Output is correct
34 Correct 153 ms 188180 KB Output is correct
35 Correct 155 ms 188232 KB Output is correct
36 Correct 154 ms 188152 KB Output is correct
37 Correct 154 ms 188288 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 188280 KB Output is correct
2 Correct 155 ms 188192 KB Output is correct
3 Correct 155 ms 188280 KB Output is correct
4 Correct 155 ms 188252 KB Output is correct
5 Correct 160 ms 188460 KB Output is correct
6 Correct 157 ms 188152 KB Output is correct
7 Correct 154 ms 188152 KB Output is correct
8 Correct 155 ms 188344 KB Output is correct
9 Correct 158 ms 188264 KB Output is correct
10 Correct 155 ms 188208 KB Output is correct
11 Correct 155 ms 188280 KB Output is correct
12 Correct 154 ms 188152 KB Output is correct
13 Correct 155 ms 188280 KB Output is correct
14 Correct 158 ms 188220 KB Output is correct
15 Correct 155 ms 188212 KB Output is correct
16 Correct 158 ms 188256 KB Output is correct
17 Correct 154 ms 188196 KB Output is correct
18 Correct 158 ms 188228 KB Output is correct
19 Correct 155 ms 188180 KB Output is correct
20 Correct 163 ms 188320 KB Output is correct
21 Correct 154 ms 188152 KB Output is correct
22 Correct 153 ms 188224 KB Output is correct
23 Correct 154 ms 188280 KB Output is correct
24 Correct 154 ms 188196 KB Output is correct
25 Correct 154 ms 188200 KB Output is correct
26 Correct 156 ms 188216 KB Output is correct
27 Correct 162 ms 188192 KB Output is correct
28 Correct 154 ms 188252 KB Output is correct
29 Correct 156 ms 188244 KB Output is correct
30 Correct 154 ms 188152 KB Output is correct
31 Correct 155 ms 188304 KB Output is correct
32 Correct 154 ms 188280 KB Output is correct
33 Correct 154 ms 188280 KB Output is correct
34 Correct 153 ms 188180 KB Output is correct
35 Correct 155 ms 188232 KB Output is correct
36 Correct 154 ms 188152 KB Output is correct
37 Correct 154 ms 188288 KB Output is correct
38 Correct 161 ms 188280 KB Output is correct
39 Correct 158 ms 188420 KB Output is correct
40 Correct 156 ms 188296 KB Output is correct
41 Correct 157 ms 188384 KB Output is correct
42 Correct 157 ms 188408 KB Output is correct
43 Correct 159 ms 188400 KB Output is correct
44 Correct 156 ms 188284 KB Output is correct
45 Correct 156 ms 188280 KB Output is correct
46 Correct 157 ms 188280 KB Output is correct
47 Correct 156 ms 188408 KB Output is correct
48 Correct 156 ms 188408 KB Output is correct
49 Correct 157 ms 188408 KB Output is correct
50 Correct 156 ms 188280 KB Output is correct
51 Correct 157 ms 188280 KB Output is correct
52 Correct 156 ms 188480 KB Output is correct
53 Correct 158 ms 188540 KB Output is correct
54 Correct 156 ms 188272 KB Output is correct
55 Correct 156 ms 188352 KB Output is correct
56 Correct 157 ms 188364 KB Output is correct
57 Correct 156 ms 188284 KB Output is correct
58 Correct 156 ms 188280 KB Output is correct
59 Correct 167 ms 188280 KB Output is correct
60 Correct 156 ms 188284 KB Output is correct
61 Correct 156 ms 188388 KB Output is correct
62 Correct 157 ms 188360 KB Output is correct
63 Correct 156 ms 188280 KB Output is correct
64 Correct 162 ms 188280 KB Output is correct
65 Correct 157 ms 188268 KB Output is correct
66 Correct 155 ms 188280 KB Output is correct
67 Correct 157 ms 188268 KB Output is correct
68 Correct 156 ms 188300 KB Output is correct
69 Correct 157 ms 188272 KB Output is correct
70 Correct 156 ms 188416 KB Output is correct
71 Correct 156 ms 188384 KB Output is correct
72 Correct 157 ms 188244 KB Output is correct
73 Correct 168 ms 188532 KB Output is correct
74 Correct 156 ms 188328 KB Output is correct

Subtask #3
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 188280 KB Output is correct
2 Correct 155 ms 188192 KB Output is correct
3 Correct 155 ms 188280 KB Output is correct
4 Correct 155 ms 188252 KB Output is correct
5 Correct 160 ms 188460 KB Output is correct
6 Correct 157 ms 188152 KB Output is correct
7 Correct 154 ms 188152 KB Output is correct
8 Correct 155 ms 188344 KB Output is correct
9 Correct 158 ms 188264 KB Output is correct
10 Correct 155 ms 188208 KB Output is correct
11 Correct 155 ms 188280 KB Output is correct
12 Correct 154 ms 188152 KB Output is correct
13 Correct 155 ms 188280 KB Output is correct
14 Correct 158 ms 188220 KB Output is correct
15 Correct 155 ms 188212 KB Output is correct
16 Correct 158 ms 188256 KB Output is correct
17 Correct 154 ms 188196 KB Output is correct
18 Correct 158 ms 188228 KB Output is correct
19 Correct 155 ms 188180 KB Output is correct
20 Correct 163 ms 188320 KB Output is correct
21 Correct 154 ms 188152 KB Output is correct
22 Correct 153 ms 188224 KB Output is correct
23 Correct 154 ms 188280 KB Output is correct
24 Correct 154 ms 188196 KB Output is correct
25 Correct 154 ms 188200 KB Output is correct
26 Correct 156 ms 188216 KB Output is correct
27 Correct 162 ms 188192 KB Output is correct
28 Correct 154 ms 188252 KB Output is correct
29 Correct 156 ms 188244 KB Output is correct
30 Correct 154 ms 188152 KB Output is correct
31 Correct 155 ms 188304 KB Output is correct
32 Correct 154 ms 188280 KB Output is correct
33 Correct 154 ms 188280 KB Output is correct
34 Correct 153 ms 188180 KB Output is correct
35 Correct 155 ms 188232 KB Output is correct
36 Correct 154 ms 188152 KB Output is correct
37 Correct 154 ms 188288 KB Output is correct
38 Correct 161 ms 188280 KB Output is correct
39 Correct 158 ms 188420 KB Output is correct
40 Correct 156 ms 188296 KB Output is correct
41 Correct 157 ms 188384 KB Output is correct
42 Correct 157 ms 188408 KB Output is correct
43 Correct 159 ms 188400 KB Output is correct
44 Correct 156 ms 188284 KB Output is correct
45 Correct 156 ms 188280 KB Output is correct
46 Correct 157 ms 188280 KB Output is correct
47 Correct 156 ms 188408 KB Output is correct
48 Correct 156 ms 188408 KB Output is correct
49 Correct 157 ms 188408 KB Output is correct
50 Correct 156 ms 188280 KB Output is correct
51 Correct 157 ms 188280 KB Output is correct
52 Correct 156 ms 188480 KB Output is correct
53 Correct 158 ms 188540 KB Output is correct
54 Correct 156 ms 188272 KB Output is correct
55 Correct 156 ms 188352 KB Output is correct
56 Correct 157 ms 188364 KB Output is correct
57 Correct 156 ms 188284 KB Output is correct
58 Correct 156 ms 188280 KB Output is correct
59 Correct 167 ms 188280 KB Output is correct
60 Correct 156 ms 188284 KB Output is correct
61 Correct 156 ms 188388 KB Output is correct
62 Correct 157 ms 188360 KB Output is correct
63 Correct 156 ms 188280 KB Output is correct
64 Correct 162 ms 188280 KB Output is correct
65 Correct 157 ms 188268 KB Output is correct
66 Correct 155 ms 188280 KB Output is correct
67 Correct 157 ms 188268 KB Output is correct
68 Correct 156 ms 188300 KB Output is correct
69 Correct 157 ms 188272 KB Output is correct
70 Correct 156 ms 188416 KB Output is correct
71 Correct 156 ms 188384 KB Output is correct
72 Correct 157 ms 188244 KB Output is correct
73 Correct 168 ms 188532 KB Output is correct
74 Correct 156 ms 188328 KB Output is correct
75 Correct 1072 ms 199572 KB Output is correct
76 Correct 1120 ms 199224 KB Output is correct
77 Correct 1087 ms 199508 KB Output is correct
78 Correct 1022 ms 199644 KB Output is correct
79 Correct 460 ms 199788 KB Output is correct
80 Correct 496 ms 199492 KB Output is correct
81 Correct 828 ms 198960 KB Output is correct
82 Correct 1002 ms 198868 KB Output is correct
83 Correct 929 ms 199380 KB Output is correct
84 Correct 960 ms 199308 KB Output is correct
85 Correct 850 ms 198840 KB Output is correct
86 Correct 578 ms 198612 KB Output is correct
87 Correct 582 ms 198480 KB Output is correct
88 Correct 761 ms 198428 KB Output is correct
89 Correct 748 ms 198996 KB Output is correct
90 Correct 603 ms 199288 KB Output is correct
91 Correct 508 ms 198480 KB Output is correct
92 Correct 520 ms 198612 KB Output is correct
93 Correct 550 ms 198868 KB Output is correct
94 Correct 512 ms 199256 KB Output is correct
95 Correct 602 ms 199328 KB Output is correct
96 Correct 389 ms 198616 KB Output is correct
97 Correct 435 ms 199252 KB Output is correct
98 Correct 410 ms 199104 KB Output is correct
99 Correct 399 ms 199136 KB Output is correct
100 Correct 414 ms 198508 KB Output is correct
101 Correct 378 ms 198804 KB Output is correct
102 Correct 904 ms 198620 KB Output is correct
103 Correct 752 ms 198484 KB Output is correct
104 Correct 840 ms 198968 KB Output is correct
105 Correct 710 ms 199052 KB Output is correct
106 Correct 865 ms 199124 KB Output is correct
107 Correct 687 ms 198872 KB Output is correct
108 Correct 970 ms 199408 KB Output is correct
109 Correct 867 ms 199908 KB Output is correct
110 Correct 437 ms 198264 KB Output is correct
111 Correct 532 ms 198228 KB Output is correct
112 Correct 400 ms 197676 KB Output is correct
113 Correct 527 ms 200224 KB Output is correct