oj.uz

Submission #1077531

# Submission time Handle Problem Language Result Execution time Memory
1077531 2024-08-27T07:53:42 Z bleahbleah Tricks of the Trade (CEOI23_trade) C++17
50 / 100
 6834 ms 36016 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;
   }
   
   private:
      ll sum = 0;
};
 
int bestcut[nmax];
ll dp[nmax];
 
ll spart[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) {
   for(int i = 1; i <= n; i++) spart[i] += spart[i - 1];   
   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 >> spart[i];
   }
   for(int i = 1; i <= n; i++)
      cin >> v[i];
   auto T = solve(n, 1);
   //reverse(spart + 1, spart + n + 1);
   //reverse(v + 1, v + n + 1);
   //auto T1 = solve(n, 0);
   //reverse(1 + all(T1));
   for(int i = 1; i <= n; i++) cout << (T[i]);
   cout << '\n';
    
 
}

Compilation message

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

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Partially correct 1 ms 512 KB Partially correct
7 Partially correct 1 ms 344 KB Partially correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Partially correct 1 ms 512 KB Partially correct
7 Partially correct 1 ms 344 KB Partially correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 1 ms 348 KB Partially correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 7 ms 1112 KB Output is correct
24 Partially correct 23 ms 772 KB Partially correct
25 Partially correct 47 ms 828 KB Partially correct
26 Partially correct 45 ms 852 KB Partially correct
27 Correct 34 ms 1108 KB Output is correct
28 Correct 9 ms 604 KB Output is correct
29 Correct 56 ms 1120 KB Output is correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Partially correct 392 ms 14364 KB Partially correct
3 Correct 551 ms 14140 KB Output is correct
4 Correct 1720 ms 22100 KB Output is correct
5 Partially correct 1699 ms 15016 KB Partially correct
6 Partially correct 1088 ms 14340 KB Partially correct
7 Correct 4263 ms 33828 KB Output is correct
8 Correct 647 ms 17232 KB Output is correct
9 Correct 563 ms 15700 KB Output is correct
10 Partially correct 530 ms 16320 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Partially correct 392 ms 14364 KB Partially correct
3 Correct 551 ms 14140 KB Output is correct
4 Correct 1720 ms 22100 KB Output is correct
5 Partially correct 1699 ms 15016 KB Partially correct
6 Partially correct 1088 ms 14340 KB Partially correct
7 Correct 4263 ms 33828 KB Output is correct
8 Correct 647 ms 17232 KB Output is correct
9 Correct 563 ms 15700 KB Output is correct
10 Partially correct 530 ms 16320 KB Partially correct
11 Correct 0 ms 348 KB Output is correct
12 Partially correct 385 ms 15336 KB Partially correct
13 Correct 623 ms 17492 KB Output is correct
14 Correct 1798 ms 25168 KB Output is correct
15 Partially correct 1679 ms 17944 KB Partially correct
16 Partially correct 1111 ms 16864 KB Partially correct
17 Correct 4352 ms 36016 KB Output is correct
18 Correct 625 ms 17592 KB Output is correct
19 Correct 577 ms 15852 KB Output is correct
20 Partially correct 529 ms 16444 KB Partially correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Partially correct 1 ms 348 KB Partially correct
26 Partially correct 1 ms 348 KB Partially correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1422 ms 17312 KB Output is correct
32 Partially correct 1624 ms 19296 KB Partially correct
33 Partially correct 3147 ms 24656 KB Partially correct
34 Partially correct 2514 ms 18668 KB Partially correct
35 Partially correct 1987 ms 18452 KB Partially correct
36 Partially correct 5433 ms 35284 KB Partially correct
37 Correct 1065 ms 15184 KB Output is correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Partially correct 1 ms 512 KB Partially correct
9 Partially correct 1 ms 344 KB Partially correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Partially correct 1 ms 348 KB Partially correct
20 Partially correct 1 ms 348 KB Partially correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 7 ms 1112 KB Output is correct
26 Partially correct 23 ms 772 KB Partially correct
27 Partially correct 47 ms 828 KB Partially correct
28 Partially correct 45 ms 852 KB Partially correct
29 Correct 34 ms 1108 KB Output is correct
30 Correct 9 ms 604 KB Output is correct
31 Correct 56 ms 1120 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Partially correct 392 ms 14364 KB Partially correct
34 Correct 551 ms 14140 KB Output is correct
35 Correct 1720 ms 22100 KB Output is correct
36 Partially correct 1699 ms 15016 KB Partially correct
37 Partially correct 1088 ms 14340 KB Partially correct
38 Correct 4263 ms 33828 KB Output is correct
39 Correct 647 ms 17232 KB Output is correct
40 Correct 563 ms 15700 KB Output is correct
41 Partially correct 530 ms 16320 KB Partially correct
42 Correct 0 ms 348 KB Output is correct
43 Partially correct 385 ms 15336 KB Partially correct
44 Correct 623 ms 17492 KB Output is correct
45 Correct 1798 ms 25168 KB Output is correct
46 Partially correct 1679 ms 17944 KB Partially correct
47 Partially correct 1111 ms 16864 KB Partially correct
48 Correct 4352 ms 36016 KB Output is correct
49 Correct 625 ms 17592 KB Output is correct
50 Correct 577 ms 15852 KB Output is correct
51 Partially correct 529 ms 16444 KB Partially correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Partially correct 1 ms 348 KB Partially correct
57 Partially correct 1 ms 348 KB Partially correct
58 Correct 1 ms 344 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 1422 ms 17312 KB Output is correct
63 Partially correct 1624 ms 19296 KB Partially correct
64 Partially correct 3147 ms 24656 KB Partially correct
65 Partially correct 2514 ms 18668 KB Partially correct
66 Partially correct 1987 ms 18452 KB Partially correct
67 Partially correct 5433 ms 35284 KB Partially correct
68 Correct 1065 ms 15184 KB Output is correct
69 Correct 1 ms 348 KB Output is correct
70 Partially correct 377 ms 15520 KB Partially correct
71 Correct 595 ms 17488 KB Output is correct
72 Correct 1734 ms 25236 KB Output is correct
73 Partially correct 1693 ms 18004 KB Partially correct
74 Partially correct 1081 ms 16880 KB Partially correct
75 Correct 4286 ms 35900 KB Output is correct
76 Correct 633 ms 17376 KB Output is correct
77 Correct 553 ms 15920 KB Output is correct
78 Partially correct 560 ms 16376 KB Partially correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 0 ms 344 KB Output is correct
81 Correct 1 ms 600 KB Output is correct
82 Correct 1 ms 344 KB Output is correct
83 Partially correct 1 ms 348 KB Partially correct
84 Partially correct 1 ms 348 KB Partially correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 1 ms 348 KB Output is correct
88 Correct 1 ms 464 KB Output is correct
89 Correct 1433 ms 17552 KB Output is correct
90 Partially correct 1704 ms 19348 KB Partially correct
91 Partially correct 3395 ms 24816 KB Partially correct
92 Partially correct 2613 ms 18684 KB Partially correct
93 Partially correct 2112 ms 18384 KB Partially correct
94 Partially correct 6351 ms 35252 KB Partially correct
95 Correct 1163 ms 15332 KB Output is correct
96 Correct 8 ms 1116 KB Output is correct
97 Partially correct 36 ms 828 KB Partially correct
98 Partially correct 71 ms 884 KB Partially correct
99 Partially correct 56 ms 860 KB Partially correct
100 Correct 37 ms 1120 KB Output is correct
101 Correct 10 ms 808 KB Output is correct
102 Correct 51 ms 1184 KB Output is correct
103 Correct 6357 ms 25204 KB Output is correct
104 Partially correct 2436 ms 18512 KB Partially correct
105 Partially correct 2833 ms 18548 KB Partially correct
106 Partially correct 4592 ms 24836 KB Partially correct
107 Partially correct 5202 ms 32000 KB Partially correct
108 Correct 6834 ms 28276 KB Output is correct
109 Correct 2817 ms 29672 KB Output is correct
110 Correct 5343 ms 34204 KB Output is correct
111 Correct 1770 ms 23664 KB Output is correct
112 Correct 2835 ms 29212 KB Output is correct