답안 #128497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128497	2019-07-11T04:00:49 Z	Lawliet	Cake 3 (JOI19_cake3)	C++14	100 / 100	1676 ms	129920 KB

cake3

#include <bits/stdc++.h>

#define MAX 200010
#define MAXV 1000000010
#define INF 1000000000000000000LL

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

class PersistentSegmentTree
{
	public:

		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );

			qtd.push_back( qtd[node] );

			sum.push_back( sum[node] );
		}

		int update(int node, int l, int r, int i)
		{
			int newNode = ++curNode;
			copy( node );

			if(l == r)
			{
				qtd[newNode]++;
				sum[newNode] += i;

				return newNode;
			}

			int m = (l + r)/2;

			if(i <= m)
			{
				int aux = update(e[newNode] , l , m , i);
				e[newNode] = aux;
			}
			else
			{
				int aux = update(d[newNode] , m + 1 , r , i);
				d[newNode] = aux;
			}

			qtd[newNode] = qtd[ e[newNode] ] + qtd[ d[newNode] ];
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		lli bs(int nodeL, int nodeR, int l, int r, lli k)
		{
			if(l == r) return k*l;

			int m = (l + r)/2;

			int qtdRight = qtd[ d[nodeR] ] - qtd[ d[nodeL] ];
			lli sumRight = sum[ d[nodeR] ] - sum[ d[nodeL] ];

			if(k <= qtdRight) return bs(d[nodeL] , d[nodeR] , m + 1 , r , k);
			return bs(e[nodeL] , e[nodeR] , l , m , k - qtdRight) + sumRight;
		}

		lli getHighests(int l, int r, int k)
		{
			return bs(root[l - 1] , root[r] , 0 , MAXV , k);
		}

		void update(int v)
		{
			curVersion++;

			root[curVersion] = update(root[curVersion - 1] , 0 , MAXV , v);
		}

		PersistentSegmentTree()
		{
			e.push_back( 0 ); d.push_back( 0 );
			qtd.push_back( 0 ); sum.push_back( 0LL );

			copy( 0 );

			root[0] = 1;

			curNode = 1;
		}

	private:

		int curNode;
		int curVersion;

		int root[MAX];

		vector<int> e, d;
		vector<int> qtd;

		vector<lli> sum;
};

int n, m;
int n1, n2;

int C[MAX];
int V[MAX];

lli ans[MAX];

vector<pii> aux;

PersistentSegmentTree SEG;

void DivAndConquer(int l, int r, int optmin, int optmax)
{
	if(l > r) return;

	int mid = (l + r)/2;

	int optInd = optmin;
	lli optAns = -INF;

	for(int g = max(mid + m - 1 , optmin) ; g <= optmax ; g++)
	{
		lli curAns = SEG.getHighests(mid + 1 , g - 1 , m - 2) - 2*C[g] + V[g];

		if(curAns > optAns)
		{
			optInd = g;
			optAns = curAns;
		}
	}

	ans[ mid ] = optAns + V[mid] + 2*C[mid];

	DivAndConquer(l , mid - 1 , optmin , optInd);
	DivAndConquer(mid + 1 , r , optInd , optmax);
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d",&n1,&n2);

		aux.push_back({n2 , n1});
	}

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

	for(int g = 0 ; g < n ; g++)
	{
		C[g + 1] = aux[g].first;
		V[g + 1] = aux[g].second;

		SEG.update( V[g + 1] );
	}

	DivAndConquer(1 , n - m + 1 , 1 , n);

	lli mx = -INF;

	for(int g = 1 ; g <= n - m + 1 ; g++)
		mx = max(mx , ans[g]);

	printf("%lld\n",mx);
}

Compilation message

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

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	508 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	2 ms	504 KB	Output is correct
26	Correct	2 ms	508 KB	Output is correct
27	Correct	2 ms	504 KB	Output is correct
28	Correct	2 ms	504 KB	Output is correct
29	Correct	2 ms	504 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	3 ms	504 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct
33	Correct	3 ms	504 KB	Output is correct
34	Correct	3 ms	504 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	504 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	508 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	2 ms	504 KB	Output is correct
26	Correct	2 ms	508 KB	Output is correct
27	Correct	2 ms	504 KB	Output is correct
28	Correct	2 ms	504 KB	Output is correct
29	Correct	2 ms	504 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	3 ms	504 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct
33	Correct	3 ms	504 KB	Output is correct
34	Correct	3 ms	504 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	504 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct
38	Correct	9 ms	1608 KB	Output is correct
39	Correct	10 ms	1736 KB	Output is correct
40	Correct	8 ms	1604 KB	Output is correct
41	Correct	8 ms	1604 KB	Output is correct
42	Correct	8 ms	1736 KB	Output is correct
43	Correct	7 ms	1604 KB	Output is correct
44	Correct	8 ms	1608 KB	Output is correct
45	Correct	8 ms	1608 KB	Output is correct
46	Correct	8 ms	1736 KB	Output is correct
47	Correct	8 ms	1608 KB	Output is correct
48	Correct	8 ms	1608 KB	Output is correct
49	Correct	8 ms	1736 KB	Output is correct
50	Correct	8 ms	1608 KB	Output is correct
51	Correct	7 ms	1608 KB	Output is correct
52	Correct	7 ms	1608 KB	Output is correct
53	Correct	7 ms	1608 KB	Output is correct
54	Correct	7 ms	1608 KB	Output is correct
55	Correct	6 ms	1608 KB	Output is correct
56	Correct	6 ms	1612 KB	Output is correct
57	Correct	6 ms	1608 KB	Output is correct
58	Correct	6 ms	1608 KB	Output is correct
59	Correct	6 ms	1608 KB	Output is correct
60	Correct	7 ms	1608 KB	Output is correct
61	Correct	6 ms	1608 KB	Output is correct
62	Correct	6 ms	1608 KB	Output is correct
63	Correct	6 ms	1736 KB	Output is correct
64	Correct	6 ms	1608 KB	Output is correct
65	Correct	7 ms	1608 KB	Output is correct
66	Correct	7 ms	1608 KB	Output is correct
67	Correct	7 ms	1608 KB	Output is correct
68	Correct	7 ms	1736 KB	Output is correct
69	Correct	7 ms	1608 KB	Output is correct
70	Correct	7 ms	1612 KB	Output is correct
71	Correct	6 ms	1608 KB	Output is correct
72	Correct	7 ms	1608 KB	Output is correct
73	Correct	10 ms	1608 KB	Output is correct
74	Correct	6 ms	1732 KB	Output is correct

Subtask #3
76.0 / 76.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	504 KB	Output is correct
19	Correct	2 ms	508 KB	Output is correct
20	Correct	2 ms	504 KB	Output is correct
21	Correct	2 ms	504 KB	Output is correct
22	Correct	2 ms	504 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	504 KB	Output is correct
25	Correct	2 ms	504 KB	Output is correct
26	Correct	2 ms	508 KB	Output is correct
27	Correct	2 ms	504 KB	Output is correct
28	Correct	2 ms	504 KB	Output is correct
29	Correct	2 ms	504 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	3 ms	504 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct
33	Correct	3 ms	504 KB	Output is correct
34	Correct	3 ms	504 KB	Output is correct
35	Correct	2 ms	376 KB	Output is correct
36	Correct	2 ms	504 KB	Output is correct
37	Correct	2 ms	504 KB	Output is correct
38	Correct	9 ms	1608 KB	Output is correct
39	Correct	10 ms	1736 KB	Output is correct
40	Correct	8 ms	1604 KB	Output is correct
41	Correct	8 ms	1604 KB	Output is correct
42	Correct	8 ms	1736 KB	Output is correct
43	Correct	7 ms	1604 KB	Output is correct
44	Correct	8 ms	1608 KB	Output is correct
45	Correct	8 ms	1608 KB	Output is correct
46	Correct	8 ms	1736 KB	Output is correct
47	Correct	8 ms	1608 KB	Output is correct
48	Correct	8 ms	1608 KB	Output is correct
49	Correct	8 ms	1736 KB	Output is correct
50	Correct	8 ms	1608 KB	Output is correct
51	Correct	7 ms	1608 KB	Output is correct
52	Correct	7 ms	1608 KB	Output is correct
53	Correct	7 ms	1608 KB	Output is correct
54	Correct	7 ms	1608 KB	Output is correct
55	Correct	6 ms	1608 KB	Output is correct
56	Correct	6 ms	1612 KB	Output is correct
57	Correct	6 ms	1608 KB	Output is correct
58	Correct	6 ms	1608 KB	Output is correct
59	Correct	6 ms	1608 KB	Output is correct
60	Correct	7 ms	1608 KB	Output is correct
61	Correct	6 ms	1608 KB	Output is correct
62	Correct	6 ms	1608 KB	Output is correct
63	Correct	6 ms	1736 KB	Output is correct
64	Correct	6 ms	1608 KB	Output is correct
65	Correct	7 ms	1608 KB	Output is correct
66	Correct	7 ms	1608 KB	Output is correct
67	Correct	7 ms	1608 KB	Output is correct
68	Correct	7 ms	1736 KB	Output is correct
69	Correct	7 ms	1608 KB	Output is correct
70	Correct	7 ms	1612 KB	Output is correct
71	Correct	6 ms	1608 KB	Output is correct
72	Correct	7 ms	1608 KB	Output is correct
73	Correct	10 ms	1608 KB	Output is correct
74	Correct	6 ms	1732 KB	Output is correct
75	Correct	1633 ms	122104 KB	Output is correct
76	Correct	1676 ms	122052 KB	Output is correct
77	Correct	1553 ms	122340 KB	Output is correct
78	Correct	1606 ms	123512 KB	Output is correct
79	Correct	561 ms	123004 KB	Output is correct
80	Correct	668 ms	122064 KB	Output is correct
81	Correct	889 ms	122040 KB	Output is correct
82	Correct	1123 ms	124068 KB	Output is correct
83	Correct	1012 ms	127940 KB	Output is correct
84	Correct	1197 ms	127660 KB	Output is correct
85	Correct	903 ms	123004 KB	Output is correct
86	Correct	661 ms	121148 KB	Output is correct
87	Correct	678 ms	121212 KB	Output is correct
88	Correct	841 ms	121308 KB	Output is correct
89	Correct	808 ms	122940 KB	Output is correct
90	Correct	675 ms	128340 KB	Output is correct
91	Correct	621 ms	121148 KB	Output is correct
92	Correct	576 ms	121328 KB	Output is correct
93	Correct	603 ms	122888 KB	Output is correct
94	Correct	559 ms	127992 KB	Output is correct
95	Correct	666 ms	128704 KB	Output is correct
96	Correct	520 ms	121148 KB	Output is correct
97	Correct	564 ms	129532 KB	Output is correct
98	Correct	593 ms	127660 KB	Output is correct
99	Correct	528 ms	127704 KB	Output is correct
100	Correct	511 ms	121148 KB	Output is correct
101	Correct	500 ms	121248 KB	Output is correct
102	Correct	761 ms	121148 KB	Output is correct
103	Correct	733 ms	121152 KB	Output is correct
104	Correct	838 ms	125456 KB	Output is correct
105	Correct	712 ms	124716 KB	Output is correct
106	Correct	725 ms	127868 KB	Output is correct
107	Correct	642 ms	123384 KB	Output is correct
108	Correct	1386 ms	122872 KB	Output is correct
109	Correct	1256 ms	129920 KB	Output is correct
110	Correct	510 ms	120636 KB	Output is correct
111	Correct	592 ms	122360 KB	Output is correct
112	Correct	1172 ms	120508 KB	Output is correct
113	Correct	571 ms	129408 KB	Output is correct

답안 #128497

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 19.0 / 19.0

Subtask #3 76.0 / 76.0

Subtask #1
5.0 / 5.0

Subtask #2
19.0 / 19.0

Subtask #3
76.0 / 76.0