oj.uz

Submission #813313

# Submission time Handle Problem Language Result Execution time Memory
813313 2023-08-07T15:38:54 Z HaroldVemeno Wiring (IOI17_wiring) C++17
17 / 100
 62 ms 11252 KB 
#include "wiring.h"
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

ll it[400000];
ll itl[400000];
int s = 1;
int n;
int m;

void radd(int l, int r, int a, int u = 1, int ul = 0, int ur = s) {
    if(r <= ul || ur <= l) return;
    if(l <= ul && ur <= r) {
        itl[u] += a;
        it[u] += a;
        return;
    }
    if(itl[u]) {
        itl[2*u] += itl[u];
        it[2*u] += itl[u];
        itl[2*u+1] += itl[u];
        it[2*u+1] += itl[u];
        itl[u] = 0;
    }
    int um = (ul + ur)/2;
    radd(l, r, a, 2*u  , ul, um);
    radd(l, r, a, 2*u+1, um, ur);
    it[u] = min(it[2*u], it[2*u+1]);
    return;
}

ll rmin(int l, int r, int u = 1, int ul = 0, int ur = s) {
    if(r <= ul || ur <= l) return 1ll << 60;
    if(l <= ul && ur <= r) {
        return it[u];
    }
    if(itl[u]) {
        itl[2*u] += itl[u];
        it[2*u] += itl[u];
        itl[2*u+1] += itl[u];
        it[2*u+1] += itl[u];
        itl[u] = 0;
    }
    int um = (ul + ur)/2;
    return min(rmin(l, r, 2*u, ul, um), rmin(l, r, 2*u+1, um, ur));

}

ll min_total_length(vector<int> r, vector<int> b) {
    n = r.size();
    m = b.size();
    vector<vector<int>> blocks;
    {
        int i = 0;
        int j = 0;
        while(i < n && j < m) {
            if(r[i] < b[j]) {
                blocks.push_back({});
                while(i < n && r[i] < b[j]) {
                    blocks.back().push_back(r[i]);
                    ++i;
                }
            } else {
                blocks.push_back({});
                while(j < m &&  b[j] < r[i]) {
                    blocks.back().push_back(b[j]);
                    j++;
                }
            }
        }
        if(i < n) {
            blocks.push_back({});
            while(i < n) {
                blocks.back().push_back(r[i]);
                ++i;
            }
        }
        if(j < m) {
            blocks.push_back({});
            while(j < m) {
                blocks.back().push_back(b[j]);
                ++j;
            }
        }
    }

    int bc = blocks.size();
    vector<vector<ll>> dp(bc);
    for(int i = 0; i < bc; ++i) {
        int bs = blocks[i].size();
        assert(bs != 0);
        dp[i].resize(bs+1);
        vector<int> ld(bs+1);
        vector<int> rd(bs+1);
        for(int j = 1; j < bs; ++j) {
            ld[j] = ld[j-1] + blocks[i][j] - blocks[i][0];
        }
        for(int j = bs-2; j >= 0; --j) {
            rd[j] = rd[j+1] + blocks[i][bs-1] - blocks[i][j];
        }
        dp[i][0] = rd[0];
        dp[i][bs] = ld[bs-1];
        for(int j = 1; j < bs; ++j) {
            dp[i][j] = rd[j] + ld[j-1];
        }
    }

    for(int i = 1; i < dp[0].size(); ++i) {
        dp[0][i] = 1ll << 60;
    }
    ifdeb {
        cout << "\n\n";
        for(auto b : dp) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
    }
    for(int i = 1; i < bc; ++i) {
        D(i)
        int lds = dp[i-1].size();
        int ds = dp[i].size();
        s = 1;
        int dist = blocks[i].front() - blocks[i-1].back();
        D(dist)
        while(s < lds) s *= 2;
        for(int j = 0; j < lds; ++j) {
            it[s+j] = dp[i-1][j] + (lds-j-1)*dist;
            D(it[s+j]);
            itl[s+j] = 0;
        }
        for(int j = lds; j < s; ++j) {
            it[s+j] = 1ll << 60;
            itl[s+j] = 0;
        }
        for(int j = s-1; j > 0; --j) {
            it[j] = min(it[2*j], it[2*j+1]);
            itl[j] = 0;
        }
        for(int j = 0; j < ds; ++j) {
            radd(max(lds-j, 0), lds, dist);
            dp[i][j] += rmin(0, lds);
            D(dp[i][j]);
        }
    }

    ifdeb {
        cout << "\n\n";
        for(auto b : blocks) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
        for(auto b : dp) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
    }

	return dp.back().back();
}

Compilation message

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i = 1; i < dp[0].size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 312 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 32 ms 9260 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '227496835'
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 39 ms 11252 KB Output is correct
4 Correct 37 ms 8692 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 40 ms 11244 KB Output is correct
19 Correct 38 ms 11136 KB Output is correct
20 Correct 36 ms 9036 KB Output is correct
21 Correct 38 ms 11224 KB Output is correct
22 Correct 38 ms 10500 KB Output is correct
23 Correct 38 ms 10472 KB Output is correct
24 Correct 38 ms 10476 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 56 ms 6204 KB Output is correct
3 Correct 32 ms 7220 KB Output is correct
4 Correct 47 ms 5844 KB Output is correct
5 Correct 32 ms 7308 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 62 ms 7764 KB Output is correct
19 Correct 51 ms 5756 KB Output is correct
20 Correct 52 ms 5820 KB Output is correct
21 Correct 60 ms 6852 KB Output is correct
22 Incorrect 58 ms 9984 KB 3rd lines differ - on the 1st token, expected: '3894937990', found: '101494282'
23 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 312 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 32 ms 9260 KB 3rd lines differ - on the 1st token, expected: '41596985758595', found: '227496835'
20 Halted 0 ms 0 KB -