oj.uz

Submission #1036704

# Submission time Handle Problem Language Result Execution time Memory
1036704 2024-07-27T15:46:39 Z Misha_Yuzvik Bulldozer (JOI17_bulldozer) C++14
80 / 100
 1006 ms 66416 KB 
# include <bits/stdc++.h>
using namespace std;
# define For(i , l , r) for(int i = (l); i <= (r); i++)
# define Rep(i , n) For(i , 0 , (n) - 1)
# define size(x) (long long)x.size()
# define MAXN 2000005
# define MAXK 1000005
# define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll inf = 1e9 + 7;
const ll mod = 1e9 + 9;
const ld eps = 0.000000001;
ll n , m , k , ans = 0 , q;
struct pt {
   ll x , y , val;
   bool operator == (const pt& p) {
       return (p.x == x && p.y == y);
   }
};
struct vc {
    ll x , y;
    ll nom1 , nom2;
};
ll cross_pr(const vc &a , const vc& b) {
  //  cout << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << "\n";
    return a.x * b.y - b.x * a.y;
}
struct node {
    ll sum , wyn , mxp , mxs;
};
vector<node>t;
ll sz = 1;
void init(ll n) {
    while (sz < n) sz *= 2;
    t.resize(sz * 3 + 5);
}
node calc(node &left , node &right) {
     node cur = {0 , 0 , 0 , 0};
     cur.sum = left.sum + right.sum;
     cur.mxp = max(left.mxp , left.sum + right.mxp);
     cur.mxs = max(right.mxs , right.sum + left.mxs);
     cur.wyn = max({left.wyn , right.wyn , left.mxs + right.mxp});
     return cur;
}
void upd(ll nom , ll val , ll x , ll lx , ll rx) {
       if (rx - lx == 1) {
            t[x].sum = val;
            t[x].mxp = t[x].mxs = t[x].wyn = max(0LL , val);
            return;
       }
       ll mid = (lx + rx) / 2;
       if (nom < mid) upd(nom , val , (x << 1) , lx , mid);
       else upd(nom , val , (x << 1) + 1 , mid , rx);
       t[x] = calc(t[x << 1] , t[(x << 1) + 1]);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    vector<pt>p(n);
    for (auto &[x , y , val] : p) cin >> x >> y >> val;
    sort(p.begin() , p.end() , 
         [](const auto& l , const auto& r) {
             if (l.x == r.x) return l.y > r.y;
             return l.x < r.x;   
         });
    vector<vc>line;
    Rep (i , n) {
        For (j , i + 1 , n - 1) {
            line.push_back({p[i].x - p[j].x , p[i].y - p[j].y , i , j});  
            if (size(line) > 0 && line.back().x == 0) line.pop_back();
            if (size(line) > 0 && line.back().x < 0) line.back().x *= -1 , line.back().y *= -1;
        }
    }
    sort(all(line) , 
       [&](const vc& l , const vc& r) {
            //  cout << 0 << endl;
              ll f = cross_pr(l , r);
              if (f == 0) {
               //   cout << 1 << endl;
                  if (p[l.nom1] == p[r.nom1]) return p[l.nom2].x < p[r.nom2].x;
                  else return p[l.nom1].x < p[r.nom1].x;
              } 
              return f < 0;
    });
    init(n);
    Rep (i , n) {
        upd(i , p[i].val , 1 , 0 , sz);
    }
    vector<ll>pos(n);
    Rep (i , n) pos[i] = i;
    ans = t[1].wyn;
    if (size(line) == 0) {
        cout << ans;
        return 0;
    }
    ld prev_tg = (ld)line[0].y / (ld)line[0].x;
    Rep (i , size(line)) {
          ll x = line[i].x , y = line[i].y , nom1 = line[i].nom1 , nom2 = line[i].nom2;
          if ((ld)y / (ld)x != prev_tg) {
            ll cur_res = t[1].wyn;
            ans = max(ans , cur_res);
            prev_tg = (ld)y / (ld)x;
          }
          swap(pos[nom1] , pos[nom2]);
          ll pos1 = pos[nom1] , pos2 = pos[nom2];
          upd(pos1 , p[nom1].val , 1 , 0 , sz);
          upd(pos2 , p[nom2].val , 1 , 0 , sz);
          
    }
    ans = max(ans , t[1].wyn);
    cout << ans;
}
/*

*/

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:62:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (auto &[x , y , val] : p) cin >> x >> y >> val;
      |                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 456 KB Output is correct
18 Correct 0 ms 504 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 732 KB Output is correct
22 Correct 2 ms 732 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 732 KB Output is correct
28 Correct 2 ms 708 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 3 ms 860 KB Output is correct
32 Correct 3 ms 860 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 456 KB Output is correct
18 Correct 0 ms 504 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 732 KB Output is correct
22 Correct 2 ms 732 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 732 KB Output is correct
28 Correct 2 ms 708 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 3 ms 860 KB Output is correct
32 Correct 3 ms 860 KB Output is correct
33 Correct 894 ms 66164 KB Output is correct
34 Correct 918 ms 66216 KB Output is correct
35 Correct 914 ms 66416 KB Output is correct
36 Correct 1006 ms 66212 KB Output is correct
37 Correct 957 ms 66164 KB Output is correct
38 Correct 977 ms 66216 KB Output is correct
39 Correct 923 ms 66260 KB Output is correct
40 Correct 989 ms 66256 KB Output is correct
41 Correct 974 ms 66140 KB Output is correct
42 Correct 929 ms 66192 KB Output is correct
43 Correct 956 ms 66248 KB Output is correct
44 Correct 908 ms 66196 KB Output is correct
45 Correct 937 ms 66164 KB Output is correct
46 Correct 952 ms 66196 KB Output is correct
47 Correct 939 ms 66244 KB Output is correct
48 Correct 926 ms 66240 KB Output is correct
49 Correct 900 ms 66280 KB Output is correct
50 Correct 944 ms 66208 KB Output is correct
51 Correct 893 ms 66196 KB Output is correct
52 Correct 907 ms 66196 KB Output is correct
53 Correct 876 ms 66160 KB Output is correct
54 Correct 859 ms 66208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 456 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 456 KB Output is correct
18 Correct 0 ms 504 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 732 KB Output is correct
22 Correct 2 ms 732 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 732 KB Output is correct
28 Correct 2 ms 708 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 3 ms 860 KB Output is correct
32 Correct 3 ms 860 KB Output is correct
33 Correct 894 ms 66164 KB Output is correct
34 Correct 918 ms 66216 KB Output is correct
35 Correct 914 ms 66416 KB Output is correct
36 Correct 1006 ms 66212 KB Output is correct
37 Correct 957 ms 66164 KB Output is correct
38 Correct 977 ms 66216 KB Output is correct
39 Correct 923 ms 66260 KB Output is correct
40 Correct 989 ms 66256 KB Output is correct
41 Correct 974 ms 66140 KB Output is correct
42 Correct 929 ms 66192 KB Output is correct
43 Correct 956 ms 66248 KB Output is correct
44 Correct 908 ms 66196 KB Output is correct
45 Correct 937 ms 66164 KB Output is correct
46 Correct 952 ms 66196 KB Output is correct
47 Correct 939 ms 66244 KB Output is correct
48 Correct 926 ms 66240 KB Output is correct
49 Correct 900 ms 66280 KB Output is correct
50 Correct 944 ms 66208 KB Output is correct
51 Correct 893 ms 66196 KB Output is correct
52 Correct 907 ms 66196 KB Output is correct
53 Correct 876 ms 66160 KB Output is correct
54 Correct 859 ms 66208 KB Output is correct
55 Correct 821 ms 66212 KB Output is correct
56 Correct 824 ms 66348 KB Output is correct
57 Correct 825 ms 66196 KB Output is correct
58 Correct 844 ms 66196 KB Output is correct
59 Correct 836 ms 66196 KB Output is correct
60 Correct 845 ms 66196 KB Output is correct
61 Correct 804 ms 66228 KB Output is correct
62 Correct 785 ms 66244 KB Output is correct
63 Correct 798 ms 66352 KB Output is correct
64 Correct 799 ms 66144 KB Output is correct
65 Correct 782 ms 66352 KB Output is correct
66 Correct 776 ms 66220 KB Output is correct
67 Correct 780 ms 66196 KB Output is correct
68 Correct 765 ms 66196 KB Output is correct
69 Correct 783 ms 66220 KB Output is correct
70 Correct 796 ms 66200 KB Output is correct
71 Correct 814 ms 66196 KB Output is correct
72 Correct 824 ms 66196 KB Output is correct
73 Correct 808 ms 66212 KB Output is correct
74 Correct 831 ms 66196 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 712 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 1112 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 456 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 456 KB Output is correct
33 Correct 0 ms 504 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 2 ms 732 KB Output is correct
37 Correct 2 ms 732 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 2 ms 856 KB Output is correct
40 Correct 2 ms 860 KB Output is correct
41 Correct 2 ms 860 KB Output is correct
42 Correct 2 ms 732 KB Output is correct
43 Correct 2 ms 708 KB Output is correct
44 Correct 2 ms 860 KB Output is correct
45 Correct 2 ms 856 KB Output is correct
46 Correct 3 ms 860 KB Output is correct
47 Correct 3 ms 860 KB Output is correct
48 Correct 894 ms 66164 KB Output is correct
49 Correct 918 ms 66216 KB Output is correct
50 Correct 914 ms 66416 KB Output is correct
51 Correct 1006 ms 66212 KB Output is correct
52 Correct 957 ms 66164 KB Output is correct
53 Correct 977 ms 66216 KB Output is correct
54 Correct 923 ms 66260 KB Output is correct
55 Correct 989 ms 66256 KB Output is correct
56 Correct 974 ms 66140 KB Output is correct
57 Correct 929 ms 66192 KB Output is correct
58 Correct 956 ms 66248 KB Output is correct
59 Correct 908 ms 66196 KB Output is correct
60 Correct 937 ms 66164 KB Output is correct
61 Correct 952 ms 66196 KB Output is correct
62 Correct 939 ms 66244 KB Output is correct
63 Correct 926 ms 66240 KB Output is correct
64 Correct 900 ms 66280 KB Output is correct
65 Correct 944 ms 66208 KB Output is correct
66 Correct 893 ms 66196 KB Output is correct
67 Correct 907 ms 66196 KB Output is correct
68 Correct 876 ms 66160 KB Output is correct
69 Correct 859 ms 66208 KB Output is correct
70 Correct 821 ms 66212 KB Output is correct
71 Correct 824 ms 66348 KB Output is correct
72 Correct 825 ms 66196 KB Output is correct
73 Correct 844 ms 66196 KB Output is correct
74 Correct 836 ms 66196 KB Output is correct
75 Correct 845 ms 66196 KB Output is correct
76 Correct 804 ms 66228 KB Output is correct
77 Correct 785 ms 66244 KB Output is correct
78 Correct 798 ms 66352 KB Output is correct
79 Correct 799 ms 66144 KB Output is correct
80 Correct 782 ms 66352 KB Output is correct
81 Correct 776 ms 66220 KB Output is correct
82 Correct 780 ms 66196 KB Output is correct
83 Correct 765 ms 66196 KB Output is correct
84 Correct 783 ms 66220 KB Output is correct
85 Correct 796 ms 66200 KB Output is correct
86 Correct 814 ms 66196 KB Output is correct
87 Correct 824 ms 66196 KB Output is correct
88 Correct 808 ms 66212 KB Output is correct
89 Correct 831 ms 66196 KB Output is correct
90 Correct 830 ms 66216 KB Output is correct
91 Correct 854 ms 66312 KB Output is correct
92 Correct 860 ms 66196 KB Output is correct
93 Correct 807 ms 66212 KB Output is correct
94 Correct 785 ms 66256 KB Output is correct
95 Correct 772 ms 66196 KB Output is correct
96 Correct 786 ms 66368 KB Output is correct
97 Correct 787 ms 66164 KB Output is correct
98 Correct 814 ms 66196 KB Output is correct
99 Correct 795 ms 66196 KB Output is correct
100 Correct 416 ms 33392 KB Output is correct
101 Correct 414 ms 33472 KB Output is correct
102 Correct 411 ms 33408 KB Output is correct
103 Correct 401 ms 33472 KB Output is correct
104 Correct 431 ms 33416 KB Output is correct
105 Correct 551 ms 66144 KB Output is correct
106 Correct 558 ms 66196 KB Output is correct
107 Correct 553 ms 66196 KB Output is correct
108 Correct 572 ms 66164 KB Output is correct
109 Correct 512 ms 66196 KB Output is correct
110 Incorrect 779 ms 66196 KB Output isn't correct
111 Halted 0 ms 0 KB -