oj.uz

Submission #1040738

# Submission time Handle Problem Language Result Execution time Memory
1040738 2024-08-01T08:50:11 Z 1557중연결요소(#11043) Tricks of the Trade (CEOI23_trade) C++17
55 / 100
 772 ms 287516 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int A[250005];
int B[250005];
int C[250005];
int D[250005];
vector<array<int, 2>> V;
int ans = -INF;
int K;
int F[250005];
struct SegTree {
    struct Node {
        int l, r, cnt, sum;
        Node():l(-1),r(-1),cnt(0),sum(0) {}
        Node(int c) : l(-1), r(-1), cnt(1), sum(c) {}
    };
    vector<Node> seg;
    vector<int> root;
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<N;i*=2) {}
        MAX = i;
        seg.clear();
        root.clear();
        seg.push_back(Node());
        root.push_back(0);
        cons(0, 0, MAX);
    }
    void cons(int n, int s, int e) {
        seg[n].cnt = 0, seg[n].sum = 0;
        int mid = s + e >> 1;
        //cout << s << ' ' << e << ' ' << v << '\n';
        if(s != mid) {
            seg[n].l = seg.size();
            seg.push_back(Node());
            cons(seg[n].l, s, mid);
            seg[n].r = seg.size();
            seg.push_back(Node());
            cons(seg[n].r, mid, e);
        }
        //cout << s << ' ' << e << ' ' << v << '\n';
        //cout << seg[v].l <<' ' << seg[v].r << '\n';
    }
    void add(int k, int v, int n2, int n, int ns, int ne) {
        seg[n2].l = seg[n].l;
        seg[n2].r = seg[n].r;
        seg[n2].cnt = seg[n].cnt + 1;
        seg[n2].sum = seg[n].sum + v;
        //cout << k << ' ' << v << ' ' << n << ' ' << ns << ' ' << ne << '\n';
        if(ns+1==ne) {
            return;
        }
        int mid = ns + ne >> 1;
        if(mid <= k) {
            seg[n2].r = seg.size();
            seg.push_back(Node());
            add(k, v, seg[n2].r, seg[n].r, mid, ne);
        }
        else {
            seg[n2].l = seg.size();
            seg.push_back(Node());
            add(k, v, seg[n2].l, seg[n].l, ns, mid);
        }
    }
    void add_node(int k, int v) {
        //cout << "ADD:" << k << ' ' << v << '\n';
        int prv = root.back();
        root.push_back(seg.size());
        seg.push_back(Node());
        add(k, v, root.back(), prv, 0, MAX);
    }
    int get_val(int n1, int n2, int ns, int ne, int k) {
        //cout << n1 << ' ' << n2 <<' ' << ns << ' ' << ne << ' ' << k << '\n';
        if(k==0) return 0;
        if(ns+1==ne) return seg[n1].sum - seg[n2].sum;
        int r1 = seg[n1].r, r2 = seg[n2].r;
        assert(r1 != -1 && r2 != -1);
        int v = seg[r1].cnt - seg[r2].cnt;
        if(v==k) {
            int res = seg[r1].sum - seg[r2].sum;
            //cout << n1 << ' ' << n2 << ' ' << res << '\n';
            return res;
        }
        int mid = ns + ne >> 1;
        if(v < k) {
            int res = seg[r1].sum - seg[r2].sum + get_val(seg[n1].l, seg[n2].l, ns, mid, k-v);
            //cout << n1 << ' ' << n2 << ' ' << res << '\n';
            return res;
        }
        int res = get_val(r1, r2, mid, ne, k);
        //cout << n1 << ' ' << n2 << ' ' << res << '\n';
        return res;
    }
    int get_calc(int s, int e, int k) {
        int res = get_val(root[e+1], root[s], 0, MAX, k);
        //cout << s+1 << ' ' << e+1 << " : " << res << '\n';
        return res;
    }
};
SegTree tree;
int G[250005];
void tree_cons(int N) {
    int i, j;
    tree.init(N+3);
    /*cout << "init done\n";
    for(i=0;i<tree.seg.size();i++) {
        cout << i << " : " << tree.seg[i].l <<' ' << tree.seg[i].r << ' ' << tree.seg[i].cnt <<' ' << tree.seg[i].sum << '\n';
    }
    for(i=0;i<tree.root.size();i++) cout <<tree.root[i] << ' ';
    cout << '\n';*/
    vector<array<int, 2>> V2;
    for(i=0;i<N;i++) V2.push_back({B[i], i});
    sort(V2.begin(),V2.end());
    for(i=0;i<N;i++) G[V2[i][1]] = i;
    for(i=0;i<N;i++) tree.add_node(G[i], B[i]);
    /*for(i=0;i<tree.seg.size();i++) {
        cout << i << " : " << tree.seg[i].l <<' ' << tree.seg[i].r << ' ' << tree.seg[i].cnt <<' ' << tree.seg[i].sum << '\n';
    }
    for(i=0;i<tree.root.size();i++) cout <<tree.root[i] << ' ';
    cout << '\n';*/
}
int calc_val(int s, int e) {
    int res = tree.get_calc(s, e, K) - (F[e] - (s-1>=0?F[s-1]:0));
    //cout << s+1 <<' ' << e+1 << " : " << res <<'\n';
    return res;
}
void calc(int s, int e) {
    int i, j;
    int ma = -INF, id = -1;
    priority_queue<int, vector<int>, greater<int>> PQ;
    int sum = 0;
    for(i=s;i<=e;i++) {
        sum -= A[i];
        bool isok = false;
        if(PQ.size() == K-1) isok = true;
        if(PQ.size() == K && PQ.top() <= B[i]) isok = true;
        PQ.push(B[i]);
        sum += B[i];
        if(PQ.size() > K) {
            sum -= PQ.top();
            PQ.pop();
        }
        if(PQ.size() < K) continue;
        if(sum > ma) {
            ma = sum;
            id = i;
        }
        if(sum > ans) {
            ans = sum;
            V.clear();
        }
        if(ans == sum && isok) {
            V.push_back({s, i});
        }
    }
}
void DnC(int s, int e, int a, int b) {
    if(s>e) return;
    int i, j;
    a = max(a, s+K-1);
    int mid = s + e >> 1;
    int ma = -INF, id = b;
    //cout <<"DNC: " << s << ' ' << e << ' ' << a << ' ' << b << '\n';
    for(i=max(mid+K-1, a); i <= b; i++) {
        int v = calc_val(mid, i);
        if(v > ma) {
            ma = v;
            id = i;
        }
    }
    C[mid] = ma, D[mid] = id;
    if(ma > ans) ans = ma;
    DnC(s, mid-1, a, id);
    DnC(mid+1, e, id, b);
}
int E[250005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N >> K;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    for(i=0;i<N;i++) F[i] = A[i];
    for(i=1;i<N;i++) F[i] += F[i-1];
    for(i=0;i<N;i++) cin >> B[i];
    tree_cons(N);
    DnC(0, N-1, 0, N-1);
    vector<int> pos;
    for(i=0;i<N;i++) {
        if(C[i]==ans) pos.push_back(i);
    }
    pos.push_back(N);
    //cout << ans << '\n';
    for(int i=0;i<pos.size();i++) {
        int n = pos[i];
        if(n==N) continue;
        V.push_back({n, D[n]});
        if(D[n]+1<pos[i+1]) {
            calc(pos[i], pos[i+1]-1);
        }
    }
    vector<vector<array<int, 2>>> in, out;
    in.resize(N);
    out.resize(N);
    int cnt = 0;
    for(auto k : V) {
        //k[0] ~ k[1]
        // kth element <= a[i] -> ?
        int v = (ans + F[k[1]] - (k[0]-1>=0?F[k[0]-1]:0)) - tree.get_calc(k[0], k[1], K-1);
        in[k[0]].push_back({v, cnt});
        out[k[1]].push_back({v, cnt});
        cnt++;
    }
    /*for(i=0;i<N;i++) cout << D[i] <<' ';
    cout << '\n';
    for(auto k : V) cout << k[0]+1 << ' ' << k[1]+1 << '\n';*/
    cout << ans <<'\n';
    set<array<int, 2>> S;
    for(i=0;i<N;i++) {
        for(auto n : in[i]) {
            S.insert(n);
        }
        if(!S.empty() && B[i] >= (*S.begin())[0]) cout << "1";
        else cout << "0";
        for(auto n : out[i]) {
            S.erase(n);
        }
    }
}

Compilation message

trade.cpp: In member function 'void SegTree::cons(long long int, long long int, long long int)':
trade.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid = s + e >> 1;
      |                   ~~^~~
trade.cpp: In member function 'void SegTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
trade.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
trade.cpp: In member function 'long long int SegTree::get_val(long long int, long long int, long long int, long long int, long long int)':
trade.cpp:87:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
trade.cpp: In function 'void tree_cons(long long int)':
trade.cpp:106:12: warning: unused variable 'j' [-Wunused-variable]
  106 |     int i, j;
      |            ^
trade.cpp: In function 'void calc(long long int, long long int)':
trade.cpp:138:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  138 |         if(PQ.size() == K-1) isok = true;
      |            ~~~~~~~~~~^~~~~~
trade.cpp:139:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  139 |         if(PQ.size() == K && PQ.top() <= B[i]) isok = true;
      |            ~~~~~~~~~~^~~~
trade.cpp:142:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  142 |         if(PQ.size() > K) {
      |            ~~~~~~~~~~^~~
trade.cpp:146:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  146 |         if(PQ.size() < K) continue;
      |            ~~~~~~~~~~^~~
trade.cpp:131:12: warning: unused variable 'j' [-Wunused-variable]
  131 |     int i, j;
      |            ^
trade.cpp:132:20: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  132 |     int ma = -INF, id = -1;
      |                    ^~
trade.cpp: In function 'void DnC(long long int, long long int, long long int, long long int)':
trade.cpp:164:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |     int mid = s + e >> 1;
      |               ~~^~~
trade.cpp:162:12: warning: unused variable 'j' [-Wunused-variable]
  162 |     int i, j;
      |            ^
trade.cpp: In function 'int main()':
trade.cpp:199:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for(int i=0;i<pos.size();i++) {
      |                 ~^~~~~~~~~~~
trade.cpp:186:12: warning: unused variable 'j' [-Wunused-variable]
  186 |     int i, j;
      |            ^

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 2 ms 12728 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct
7 Correct 1 ms 12892 KB Output is correct
8 Correct 1 ms 12892 KB Output is correct
9 Correct 1 ms 12892 KB Output is correct
10 Correct 1 ms 12904 KB Output is correct
11 Partially correct 1 ms 12892 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 2 ms 12728 KB Output is correct
6 Correct 1 ms 12892 KB Output is correct
7 Correct 1 ms 12892 KB Output is correct
8 Correct 1 ms 12892 KB Output is correct
9 Correct 1 ms 12892 KB Output is correct
10 Correct 1 ms 12904 KB Output is correct
11 Partially correct 1 ms 12892 KB Partially correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 1 ms 12636 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 1 ms 12892 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 1 ms 12892 KB Output is correct
19 Correct 1 ms 12892 KB Output is correct
20 Correct 1 ms 12892 KB Output is correct
21 Correct 1 ms 12892 KB Output is correct
22 Partially correct 1 ms 12892 KB Partially correct
23 Correct 4 ms 16336 KB Output is correct
24 Correct 8 ms 16720 KB Output is correct
25 Correct 8 ms 16592 KB Output is correct
26 Correct 9 ms 16336 KB Output is correct
27 Correct 7 ms 16692 KB Output is correct
28 Correct 5 ms 16336 KB Output is correct
29 Correct 6 ms 16336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 291 ms 284460 KB Output is correct
3 Correct 335 ms 286896 KB Output is correct
4 Correct 628 ms 285584 KB Output is correct
5 Correct 617 ms 283572 KB Output is correct
6 Correct 451 ms 286248 KB Output is correct
7 Correct 744 ms 285448 KB Output is correct
8 Correct 319 ms 285588 KB Output is correct
9 Correct 300 ms 284316 KB Output is correct
10 Correct 347 ms 285668 KB Output is correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 291 ms 284460 KB Output is correct
3 Correct 335 ms 286896 KB Output is correct
4 Correct 628 ms 285584 KB Output is correct
5 Correct 617 ms 283572 KB Output is correct
6 Correct 451 ms 286248 KB Output is correct
7 Correct 744 ms 285448 KB Output is correct
8 Correct 319 ms 285588 KB Output is correct
9 Correct 300 ms 284316 KB Output is correct
10 Correct 347 ms 285668 KB Output is correct
11 Correct 1 ms 12632 KB Output is correct
12 Correct 289 ms 285348 KB Output is correct
13 Correct 311 ms 283272 KB Output is correct
14 Correct 587 ms 283540 KB Output is correct
15 Correct 563 ms 284308 KB Output is correct
16 Correct 454 ms 282716 KB Output is correct
17 Correct 723 ms 284300 KB Output is correct
18 Correct 307 ms 283028 KB Output is correct
19 Correct 292 ms 283028 KB Output is correct
20 Correct 360 ms 283600 KB Output is correct
21 Correct 1 ms 12636 KB Output is correct
22 Correct 1 ms 12636 KB Output is correct
23 Correct 1 ms 12892 KB Output is correct
24 Correct 1 ms 12892 KB Output is correct
25 Correct 1 ms 12892 KB Output is correct
26 Correct 1 ms 12892 KB Output is correct
27 Correct 1 ms 12892 KB Output is correct
28 Correct 1 ms 12892 KB Output is correct
29 Correct 1 ms 12892 KB Output is correct
30 Partially correct 2 ms 12892 KB Partially correct
31 Correct 367 ms 282884 KB Output is correct
32 Correct 590 ms 282772 KB Output is correct
33 Correct 648 ms 283300 KB Output is correct
34 Correct 539 ms 283284 KB Output is correct
35 Correct 456 ms 285332 KB Output is correct
36 Correct 700 ms 284812 KB Output is correct
37 Correct 395 ms 284820 KB Output is correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12728 KB Output is correct
8 Correct 1 ms 12892 KB Output is correct
9 Correct 1 ms 12892 KB Output is correct
10 Correct 1 ms 12892 KB Output is correct
11 Correct 1 ms 12892 KB Output is correct
12 Correct 1 ms 12904 KB Output is correct
13 Partially correct 1 ms 12892 KB Partially correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 1 ms 12892 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 1 ms 12892 KB Output is correct
21 Correct 1 ms 12892 KB Output is correct
22 Correct 1 ms 12892 KB Output is correct
23 Correct 1 ms 12892 KB Output is correct
24 Partially correct 1 ms 12892 KB Partially correct
25 Correct 4 ms 16336 KB Output is correct
26 Correct 8 ms 16720 KB Output is correct
27 Correct 8 ms 16592 KB Output is correct
28 Correct 9 ms 16336 KB Output is correct
29 Correct 7 ms 16692 KB Output is correct
30 Correct 5 ms 16336 KB Output is correct
31 Correct 6 ms 16336 KB Output is correct
32 Correct 1 ms 12632 KB Output is correct
33 Correct 291 ms 284460 KB Output is correct
34 Correct 335 ms 286896 KB Output is correct
35 Correct 628 ms 285584 KB Output is correct
36 Correct 617 ms 283572 KB Output is correct
37 Correct 451 ms 286248 KB Output is correct
38 Correct 744 ms 285448 KB Output is correct
39 Correct 319 ms 285588 KB Output is correct
40 Correct 300 ms 284316 KB Output is correct
41 Correct 347 ms 285668 KB Output is correct
42 Correct 1 ms 12632 KB Output is correct
43 Correct 289 ms 285348 KB Output is correct
44 Correct 311 ms 283272 KB Output is correct
45 Correct 587 ms 283540 KB Output is correct
46 Correct 563 ms 284308 KB Output is correct
47 Correct 454 ms 282716 KB Output is correct
48 Correct 723 ms 284300 KB Output is correct
49 Correct 307 ms 283028 KB Output is correct
50 Correct 292 ms 283028 KB Output is correct
51 Correct 360 ms 283600 KB Output is correct
52 Correct 1 ms 12636 KB Output is correct
53 Correct 1 ms 12636 KB Output is correct
54 Correct 1 ms 12892 KB Output is correct
55 Correct 1 ms 12892 KB Output is correct
56 Correct 1 ms 12892 KB Output is correct
57 Correct 1 ms 12892 KB Output is correct
58 Correct 1 ms 12892 KB Output is correct
59 Correct 1 ms 12892 KB Output is correct
60 Correct 1 ms 12892 KB Output is correct
61 Partially correct 2 ms 12892 KB Partially correct
62 Correct 367 ms 282884 KB Output is correct
63 Correct 590 ms 282772 KB Output is correct
64 Correct 648 ms 283300 KB Output is correct
65 Correct 539 ms 283284 KB Output is correct
66 Correct 456 ms 285332 KB Output is correct
67 Correct 700 ms 284812 KB Output is correct
68 Correct 395 ms 284820 KB Output is correct
69 Correct 1 ms 12632 KB Output is correct
70 Correct 288 ms 284208 KB Output is correct
71 Correct 315 ms 287516 KB Output is correct
72 Correct 598 ms 286360 KB Output is correct
73 Correct 550 ms 286300 KB Output is correct
74 Correct 454 ms 285592 KB Output is correct
75 Correct 772 ms 284300 KB Output is correct
76 Correct 297 ms 284056 KB Output is correct
77 Correct 309 ms 283348 KB Output is correct
78 Correct 345 ms 284308 KB Output is correct
79 Correct 1 ms 12632 KB Output is correct
80 Correct 1 ms 12636 KB Output is correct
81 Correct 2 ms 12892 KB Output is correct
82 Correct 2 ms 12892 KB Output is correct
83 Correct 1 ms 12892 KB Output is correct
84 Correct 1 ms 12892 KB Output is correct
85 Correct 1 ms 12892 KB Output is correct
86 Correct 1 ms 12892 KB Output is correct
87 Correct 1 ms 12892 KB Output is correct
88 Partially correct 1 ms 12892 KB Partially correct
89 Correct 360 ms 286100 KB Output is correct
90 Correct 598 ms 284564 KB Output is correct
91 Correct 650 ms 285668 KB Output is correct
92 Correct 558 ms 286096 KB Output is correct
93 Correct 440 ms 286860 KB Output is correct
94 Correct 744 ms 283536 KB Output is correct
95 Correct 388 ms 283608 KB Output is correct
96 Correct 5 ms 16336 KB Output is correct
97 Correct 8 ms 17104 KB Output is correct
98 Correct 8 ms 16324 KB Output is correct
99 Correct 9 ms 16592 KB Output is correct
100 Correct 7 ms 17616 KB Output is correct
101 Correct 6 ms 16104 KB Output is correct
102 Correct 7 ms 16332 KB Output is correct
103 Correct 374 ms 287212 KB Output is correct
104 Correct 474 ms 285068 KB Output is correct
105 Correct 536 ms 285328 KB Output is correct
106 Correct 760 ms 286012 KB Output is correct
107 Correct 191 ms 286356 KB Output is correct
108 Correct 453 ms 286160 KB Output is correct
109 Correct 429 ms 285332 KB Output is correct
110 Correct 467 ms 284304 KB Output is correct
111 Correct 216 ms 286580 KB Output is correct
112 Partially correct 559 ms 284556 KB Partially correct