oj.uz

Submission #1077552

# Submission time Handle Problem Language Result Execution time Memory
1077552 2024-08-27T07:59:26 Z bleahbleah Tricks of the Trade (CEOI23_trade) C++17
50 / 100
 7697 ms 39916 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
 
using ll = long long;
using ld = long double;
 
#define int ll
#define sz(x) ((int)(x).size())
 
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
const int nmax = 25e4 + 5;
 
int K;
 
const ll inf = 1e18;
 
struct KthHeap {
   multiset<int> outside, inside;
   void repair() {
      while(sz(inside) > K) {
         int x = *inside.begin();
         inside.erase(inside.find(x));
         outside.insert(x);
         sum -= x;
      }
      while(sz(inside) < K && sz(outside)) {
         int x = *outside.rbegin();
         outside.erase(outside.find(x));
         inside.insert(x);
         sum += x;
      }
      while(sz(inside) && sz(outside) && *inside.begin() < *outside.rbegin()) {
         int x = *outside.rbegin(), y = *inside.begin();
         outside.erase(outside.find(x));
         inside.erase(inside.find(y));
         outside.emplace(y);
         inside.emplace(x);
         sum += x - y;
      }
      return;
   }
   void erase(int x) {
      if(outside.find(x) != outside.end())
         outside.erase(outside.find(x));
      else if(inside.find(x) != inside.end())
         inside.erase(inside.find(x)), sum -= x;
      else assert(false);
      repair();
   }
   void insert(int x) {
      outside.emplace(x);
      repair();
   }
   ll query() {
      repair();
      if(sz(inside) < K) return -inf;
      return sum;
   }
   void clear() { inside.clear(); outside.clear(); }
   
   private:
      ll sum = 0;
};
 
int bestcut[nmax];
ll dp[nmax];
 
ll spart[nmax];
ll SS[nmax];
ll v[nmax];
ll V[nmax];
 
ll S(int l, int r) { return spart[r] - spart[l - 1]; }
 
namespace Divide {
   KthHeap hint;
   
   void divide(int l, int r) {
      if(l + 1 == r) return;
      int optl = bestcut[l], optr = bestcut[r];
      
      int mid = l + r >> 1;
      if(r <= optl) {
         for(int i = mid; i < r; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, optl);
         int atr = optl;
         for(int i = optl + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         bestcut[mid] = atr, dp[mid] = best;
         if(atr - mid + 1 == K) {
            int SA = S(mid, atr), SB = 0;
            for(int i = mid; i <= atr; i++) SB += v[i];
         }
         
         for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i < r; i++) hint.erase(v[i]);
         for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]);
         divide(mid, r);
         for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]);
      }
      else {
         int border = max(mid - 1, optl);
         for(int i = mid; i <= border; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, border), atr = border;
         for(int i = border + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         
         bestcut[mid] = atr, dp[mid] = best;
         
         for(int i = optr; i > border; i--) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i <= border; i++) hint.erase(v[i]);
         for(int i = r; i <= atr; i++) hint.insert(v[i]);
         divide(mid, r);
         for(int i = r; i <= atr; i++) hint.erase(v[i]);
      }
   }
   
}
 
 
vector<int> solve(int n, bool first = 1) {
   Divide::hint.clear();
   for(int i = 1; i <= n; i++) spart[i] = SS[i] + spart[i - 1], dp[i] = -inf, bestcut[i] = 0;
   bestcut[0] = 0;
   bestcut[n - K + 2] = n;
   Divide::divide(0, n - K + 2);
   ll mx = -inf;
   
   vector<int> possible(n + 1);
   
   
   for(int i = 1; i <= n - K + 1; i++) 
      mx = max(mx, dp[i]);
   if(first)
      cout << mx << '\n';
   
   auto cmp = [&](int a, int b) { return (v[a] < v[b] || (v[a] == v[b] && a < b)); };
   set<int, decltype(cmp)> inside(cmp), outside(cmp);
   
   int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
   
   KthHeap forchristsake;
   
   
   for(int i = 1; i <= n; i++) {
      //cerr << i << ' ' << bestcut[i] << ' ' << forchristsake.query() << '\t';
      //for(auto x : forchristsake.inside) cerr << x << ' ';
      //for(auto x : forchristsake.outside) cerr << x << ' ';
      //cerr << '\n';
      
      for(int j = bestcut[i - 1] + 1; j <= bestcut[i]; j++) {
         forchristsake.insert(v[j]);
         inside.insert(j);
         while(sz(inside) > K && [&]() {
           auto it = inside.begin(), it2 = next(it);
            return v[*it] < v[*it2];
         }()) {
            auto t = *inside.begin();
            if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
            inside.erase(inside.begin());
            outside.insert(t);
         }
         //cerr << '\t' << i << ' ' << j << ' ' << forchristsake.query() << ' ' << S(i, j) << '\n';
         if(forchristsake.query() - S(i, j) == mx) {            
            criteriaIR = bestcut[i];
            criteriaV = v[*inside.begin()];
         }
      }
      if(dp[i] == mx) {
         criteriaIR = bestcut[i];
         criteriaV = v[*inside.begin()];
         //for(auto x : inside) cerr << x << ' ';
         //cerr << '\n';
         //cerr << criteriaIR << ' ' << criteriaV << '\n';
      }
      
      forchristsake.erase(v[i]);
      if(inside.count(i)) {
         if(criteriaIR >= i && v[i] >= criteriaV) possible[i] = 1;
         inside.erase(i); 
      }
      else if(outside.count(i)) outside.erase(i);
      while(sz(inside) < K && sz(outside)) {
         int a = *outside.rbegin();
         outside.erase(a);
         inside.insert(a);
      }
   }
   
   while(!inside.empty()) {
      int t = *inside.begin();
      //cerr << t << ' ' << (t <= criteriaIR && v[t] >= criteriaV) << '\n';
      if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
      inside.erase(inside.begin());
   }
   for(int i = n; i > 0; i--) spart[i] -= spart[i - 1];
   
   return possible;
}
 
signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n >> K;
   for(int i = 1; i <= n; i++) {
      cin >> SS[i];
   }
   for(int i = 1; i <= n; i++)
      cin >> v[i], V[i] = v[i];
   //auto T = solve(n, 1);
   reverse(SS + 1, SS + n + 1);
   reverse(V + 1, V + n + 1);
   for(int i = 1; i <= n; i++) v[i] = V[i];
   auto T1 = solve(n, 1);
   for(int i = 1; i <= n; i++) cout << (T1[n - i + 1]);
   cout << '\n';
    
 
}

Compilation message

trade.cpp: In function 'void Divide::divide(ll, ll)':
trade.cpp:85:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:96:17: warning: unused variable 'SA' [-Wunused-variable]
   96 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'std::vector<long long int> solve(ll, bool)':
trade.cpp:149:8: warning: unused variable 'criteriaIL' [-Wunused-variable]
  149 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |        ^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Correct 1 ms 348 KB Output is correct
9 Partially correct 1 ms 348 KB Partially correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Partially correct 1 ms 348 KB Partially correct
7 Partially correct 1 ms 348 KB Partially correct
8 Correct 1 ms 348 KB Output is correct
9 Partially correct 1 ms 348 KB Partially correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 460 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 1 ms 484 KB Partially correct
19 Correct 1 ms 348 KB Output is correct
20 Partially correct 1 ms 604 KB Partially correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 7 ms 1372 KB Output is correct
24 Partially correct 27 ms 860 KB Partially correct
25 Partially correct 55 ms 1104 KB Partially correct
26 Partially correct 40 ms 988 KB Partially correct
27 Correct 29 ms 1116 KB Output is correct
28 Correct 9 ms 968 KB Output is correct
29 Correct 36 ms 1108 KB Output is correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 379 ms 19040 KB Partially correct
3 Correct 547 ms 20892 KB Output is correct
4 Correct 1736 ms 28584 KB Output is correct
5 Partially correct 1702 ms 21760 KB Partially correct
6 Partially correct 1076 ms 20420 KB Partially correct
7 Partially correct 4715 ms 39764 KB Partially correct
8 Correct 681 ms 21344 KB Output is correct
9 Correct 627 ms 19536 KB Output is correct
10 Partially correct 541 ms 20308 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 379 ms 19040 KB Partially correct
3 Correct 547 ms 20892 KB Output is correct
4 Correct 1736 ms 28584 KB Output is correct
5 Partially correct 1702 ms 21760 KB Partially correct
6 Partially correct 1076 ms 20420 KB Partially correct
7 Partially correct 4715 ms 39764 KB Partially correct
8 Correct 681 ms 21344 KB Output is correct
9 Correct 627 ms 19536 KB Output is correct
10 Partially correct 541 ms 20308 KB Partially correct
11 Correct 1 ms 344 KB Output is correct
12 Partially correct 425 ms 19284 KB Partially correct
13 Correct 541 ms 21164 KB Output is correct
14 Correct 1815 ms 29092 KB Output is correct
15 Partially correct 1699 ms 21844 KB Partially correct
16 Partially correct 1067 ms 20672 KB Partially correct
17 Partially correct 4772 ms 39916 KB Partially correct
18 Correct 637 ms 21328 KB Output is correct
19 Correct 560 ms 19796 KB Output is correct
20 Partially correct 548 ms 20308 KB Partially correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Partially correct 1 ms 348 KB Partially correct
26 Partially correct 1 ms 532 KB Partially correct
27 Correct 1 ms 348 KB Output is correct
28 Partially correct 2 ms 348 KB Partially correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1453 ms 21316 KB Output is correct
32 Partially correct 1720 ms 23084 KB Partially correct
33 Partially correct 3384 ms 28604 KB Partially correct
34 Partially correct 2496 ms 22512 KB Partially correct
35 Partially correct 2067 ms 22364 KB Partially correct
36 Partially correct 5596 ms 39152 KB Partially correct
37 Correct 1098 ms 19304 KB Output is correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Partially correct 1 ms 348 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Correct 1 ms 348 KB Output is correct
11 Partially correct 1 ms 348 KB Partially correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 460 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Partially correct 1 ms 348 KB Partially correct
20 Partially correct 1 ms 484 KB Partially correct
21 Correct 1 ms 348 KB Output is correct
22 Partially correct 1 ms 604 KB Partially correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 7 ms 1372 KB Output is correct
26 Partially correct 27 ms 860 KB Partially correct
27 Partially correct 55 ms 1104 KB Partially correct
28 Partially correct 40 ms 988 KB Partially correct
29 Correct 29 ms 1116 KB Output is correct
30 Correct 9 ms 968 KB Output is correct
31 Correct 36 ms 1108 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Partially correct 379 ms 19040 KB Partially correct
34 Correct 547 ms 20892 KB Output is correct
35 Correct 1736 ms 28584 KB Output is correct
36 Partially correct 1702 ms 21760 KB Partially correct
37 Partially correct 1076 ms 20420 KB Partially correct
38 Partially correct 4715 ms 39764 KB Partially correct
39 Correct 681 ms 21344 KB Output is correct
40 Correct 627 ms 19536 KB Output is correct
41 Partially correct 541 ms 20308 KB Partially correct
42 Correct 1 ms 344 KB Output is correct
43 Partially correct 425 ms 19284 KB Partially correct
44 Correct 541 ms 21164 KB Output is correct
45 Correct 1815 ms 29092 KB Output is correct
46 Partially correct 1699 ms 21844 KB Partially correct
47 Partially correct 1067 ms 20672 KB Partially correct
48 Partially correct 4772 ms 39916 KB Partially correct
49 Correct 637 ms 21328 KB Output is correct
50 Correct 560 ms 19796 KB Output is correct
51 Partially correct 548 ms 20308 KB Partially correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Partially correct 1 ms 348 KB Partially correct
57 Partially correct 1 ms 532 KB Partially correct
58 Correct 1 ms 348 KB Output is correct
59 Partially correct 2 ms 348 KB Partially correct
60 Correct 2 ms 596 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 1453 ms 21316 KB Output is correct
63 Partially correct 1720 ms 23084 KB Partially correct
64 Partially correct 3384 ms 28604 KB Partially correct
65 Partially correct 2496 ms 22512 KB Partially correct
66 Partially correct 2067 ms 22364 KB Partially correct
67 Partially correct 5596 ms 39152 KB Partially correct
68 Correct 1098 ms 19304 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Partially correct 399 ms 19284 KB Partially correct
71 Correct 588 ms 21164 KB Output is correct
72 Correct 1873 ms 29012 KB Output is correct
73 Partially correct 1911 ms 22016 KB Partially correct
74 Partially correct 1135 ms 20820 KB Partially correct
75 Partially correct 5404 ms 39916 KB Partially correct
76 Correct 723 ms 21340 KB Output is correct
77 Correct 695 ms 19772 KB Output is correct
78 Partially correct 694 ms 20400 KB Partially correct
79 Correct 1 ms 348 KB Output is correct
80 Correct 1 ms 348 KB Output is correct
81 Correct 1 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Partially correct 1 ms 348 KB Partially correct
84 Partially correct 2 ms 344 KB Partially correct
85 Correct 1 ms 344 KB Output is correct
86 Partially correct 1 ms 348 KB Partially correct
87 Correct 1 ms 348 KB Output is correct
88 Correct 1 ms 344 KB Output is correct
89 Correct 1615 ms 21352 KB Output is correct
90 Partially correct 1718 ms 23168 KB Partially correct
91 Partially correct 3584 ms 28604 KB Partially correct
92 Partially correct 2856 ms 22512 KB Partially correct
93 Partially correct 2124 ms 22364 KB Partially correct
94 Partially correct 6073 ms 39196 KB Partially correct
95 Correct 1054 ms 19096 KB Output is correct
96 Correct 7 ms 1372 KB Output is correct
97 Partially correct 33 ms 992 KB Partially correct
98 Partially correct 46 ms 1048 KB Partially correct
99 Partially correct 41 ms 976 KB Partially correct
100 Correct 31 ms 1104 KB Output is correct
101 Correct 9 ms 856 KB Output is correct
102 Correct 36 ms 1064 KB Output is correct
103 Correct 6431 ms 31192 KB Output is correct
104 Partially correct 2665 ms 20368 KB Partially correct
105 Partially correct 2978 ms 22496 KB Partially correct
106 Partially correct 4685 ms 28696 KB Partially correct
107 Partially correct 5662 ms 39784 KB Partially correct
108 Partially correct 7697 ms 34200 KB Partially correct
109 Correct 3237 ms 35316 KB Output is correct
110 Partially correct 6798 ms 39344 KB Partially correct
111 Correct 1979 ms 29384 KB Output is correct
112 Correct 2995 ms 34076 KB Output is correct