Submission #881480

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
881480	2023-12-01 09:38:49	eitanelb	Cultivation (JOI17_cultivation)	C++14	100 / 100	612 ms	161620 KiB

cultivation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<vector>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
/*
for down - just real distances from down (optional also for left) -> O(n)
for up - just real distances, or such that together it's distance between two -> O(n)+O(n^2)
after I have up and down - O(n^2) //optional - O(nlogu), with segmentree sparse/coordination, then O(n^4 logU)
then O(n^5), or if r<=40 -> O(40*40*40*n)
which is 60 points
for 100 points, let's see that whenever you get the up bigger, it affects only one place
that can being it to O(n^3), which is 100 points
*/
int deb = 0;
pair<int, pi>* merge(pair<int, pi>* v1, pair<int, pi>* v2, int n1, int n2) {
  pair<int, pi>* v3 = new pair<int,pi>[n1+n2];
  int p1 = 0, p2 = 0, p3=0;
  while (p1 < n1 || p2 < n2) {
    if (p1 != n1 && (p2 == n2 || v1[p1].x <= v2[p2].x)) v3[p3++] = v1[p1++];
    else v3[p3++] = v2[p2++];
  }
  return v3;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 20 / 20