oj.uz

Submission #46956

# Submission time Handle Problem Language Result Execution time Memory
46956 2018-04-25T11:16:41 Z SpaimaCarpatilor Wiring (IOI17_wiring) C++17
100 / 100
 186 ms 95692 KB 
#include "wiring.h"
#include<bits/stdc++.h>

using namespace std;

int N, x[200009], col[200009], st[200009], dr[200009], minD[200009];
long long dp[200009], s[200009];
const int INF = 1e9 + 100;

void init (vector < int > &rr, vector < int > &bb)
{
    int pntr1 = 0, pntr2 = 0;
    while (pntr1 < rr.size () || pntr2 < bb.size ())
    {
        if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
            x[++N] = rr[pntr1], pntr1 ++, col[N] = 0;
        else
            x[++N] = bb[pntr2], pntr2 ++, col[N] = 1;
    }
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        if (lst[col[i] ^ 1] == -1) minD[i] = INF;
        else minD[i] = x[i] - lst[col[i] ^ 1];
        lst[col[i]] = x[i];
    }
    lst[0] = lst[1] = -1;
    for (int i=N; i>=1; i--)
    {
        if (lst[col[i] ^ 1] != -1)
            minD[i] = min (minD[i], lst[col[i] ^ 1] - x[i]);
        lst[col[i]] = x[i];
    }
    for (int i=1; i<=N; i++)
        s[i] = s[i - 1] + x[i];
    for (int i=1; i<=N; i++)
        if (col[i] != col[i - 1] || i == 1) st[i] = i;
        else st[i] = st[i - 1];
    for (int i=N; i>=1; i--)
        if (col[i] != col[i + 1] || i == N) dr[i] = i;
        else dr[i] = dr[i + 1];
}
namespace segtree {
    long long arb[2][560009], minQ;

    void Update (int lin, int nod, int st, int dr, int pos, long long val)
    {
        if (st == dr)
        {
            arb[lin][nod] = val;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) Update (lin, f1, st, mij, pos, val);
        else Update (lin, f2, mij + 1, dr, pos, val);
        arb[lin][nod] = min (arb[lin][f1], arb[lin][f2]);
    }

    void Query (int lin, int nod, int st, int dr, int x, int y)
    {
        if (x <= st && dr <= y)
        {
            if (x == st || arb[lin][nod] < minQ)
                minQ = arb[lin][nod];
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= mij) Query (lin, f1, st, mij, x, y);
        if (mij < y) Query (lin, f2, mij + 1, dr, x, y);
    }

    void performUpdate (int lin, int pos, long long val)
    {
        Update (lin, 1, 1, N, pos, val);
    }

    long long askQuery (int lin, int st, int dr)
    {
        minQ = 1LL << 60;
        st = max (1, st);
        if (st <= dr)
            Query (lin, 1, 1, N, st, dr);
        return minQ;
    }
}
using namespace segtree;

long long min_total_length (vector < int > rr, vector < int > bb)
{
    init (rr, bb);
    dp[0] = 0;
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        dp[i] = dp[i - 1] + minD[i];
        if (st[i] > 1)
        {
            int k = st[i] - 1, till = st[k];
            long long mini = 1LL << 60;
            {
                //j >= 2 + 2k - i
                long long curr = askQuery (0, max (st[k], 2 + 2 * k - i), k);
                curr -= 1LL * x[k] * (i - 2 * k - 1);
                if (curr < mini)
                    mini = curr;
            }
            {
                long long curr = askQuery (1, st[k], min (k, 1 + 2 * k - i));
                curr += 1LL * x[k + 1] * (2 * k - i + 1);
                if (curr < mini)
                    mini = curr;
            }
            mini += s[i] - 2LL * s[k];
            if (mini < dp[i])
                dp[i] = mini;
        }
        ///udpates
        performUpdate (0, i, dp[i - 1] + s[i - 1] - 1LL * x[dr[i]] * i);
        performUpdate (1, i, dp[i - 1] + s[i - 1] - 1LL * x[dr[i] + 1] * i);
    }
/*    for (int i=1; i<=N; i++)
        printf ("%lld ", dp[i]);
    printf ("\n");*/
	return dp[N];
}

Compilation message

wiring.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
wiring.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
            ~~~~~~^~~~~~~~~~~~
wiring.cpp:13:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
                                  ~~~~~~^~~~~~~~~~~~
wiring.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
             ~~~~~~^~~~~~~~~~~~~
wiring.cpp:15:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
                                     ~~~~~~^~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:100:32: warning: unused variable 'till' [-Wunused-variable]
             int k = st[i] - 1, till = st[k];
                                ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 2 ms 696 KB Output is correct
16 Correct 2 ms 696 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 696 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 100 ms 16780 KB Output is correct
4 Correct 99 ms 18248 KB Output is correct
5 Correct 105 ms 19716 KB Output is correct
6 Correct 149 ms 23744 KB Output is correct
7 Correct 142 ms 25800 KB Output is correct
8 Correct 132 ms 27632 KB Output is correct
9 Correct 132 ms 29688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29688 KB Output is correct
2 Correct 2 ms 29688 KB Output is correct
3 Correct 164 ms 29688 KB Output is correct
4 Correct 154 ms 29688 KB Output is correct
5 Correct 2 ms 29688 KB Output is correct
6 Correct 2 ms 29688 KB Output is correct
7 Correct 2 ms 29688 KB Output is correct
8 Correct 2 ms 29688 KB Output is correct
9 Correct 2 ms 29688 KB Output is correct
10 Correct 2 ms 29688 KB Output is correct
11 Correct 2 ms 29688 KB Output is correct
12 Correct 2 ms 29688 KB Output is correct
13 Correct 2 ms 29688 KB Output is correct
14 Correct 2 ms 29688 KB Output is correct
15 Correct 2 ms 29688 KB Output is correct
16 Correct 2 ms 29688 KB Output is correct
17 Correct 2 ms 29688 KB Output is correct
18 Correct 157 ms 29688 KB Output is correct
19 Correct 182 ms 29688 KB Output is correct
20 Correct 153 ms 29688 KB Output is correct
21 Correct 143 ms 29688 KB Output is correct
22 Correct 147 ms 29688 KB Output is correct
23 Correct 143 ms 29688 KB Output is correct
24 Correct 146 ms 29688 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 29688 KB Output is correct
2 Correct 181 ms 30836 KB Output is correct
3 Correct 137 ms 32240 KB Output is correct
4 Correct 145 ms 33408 KB Output is correct
5 Correct 136 ms 34728 KB Output is correct
6 Correct 2 ms 34728 KB Output is correct
7 Correct 2 ms 34728 KB Output is correct
8 Correct 2 ms 34728 KB Output is correct
9 Correct 2 ms 34728 KB Output is correct
10 Correct 2 ms 34728 KB Output is correct
11 Correct 2 ms 34728 KB Output is correct
12 Correct 2 ms 34728 KB Output is correct
13 Correct 2 ms 34728 KB Output is correct
14 Correct 2 ms 34728 KB Output is correct
15 Correct 2 ms 34728 KB Output is correct
16 Correct 2 ms 34728 KB Output is correct
17 Correct 2 ms 34728 KB Output is correct
18 Correct 164 ms 36068 KB Output is correct
19 Correct 166 ms 37216 KB Output is correct
20 Correct 155 ms 38560 KB Output is correct
21 Correct 163 ms 39732 KB Output is correct
22 Correct 153 ms 41068 KB Output is correct
23 Correct 131 ms 42336 KB Output is correct
24 Correct 150 ms 43576 KB Output is correct

Subtask #5
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 3 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 2 ms 696 KB Output is correct
16 Correct 2 ms 696 KB Output is correct
17 Correct 2 ms 696 KB Output is correct
18 Correct 2 ms 764 KB Output is correct
19 Correct 100 ms 16780 KB Output is correct
20 Correct 99 ms 18248 KB Output is correct
21 Correct 105 ms 19716 KB Output is correct
22 Correct 149 ms 23744 KB Output is correct
23 Correct 142 ms 25800 KB Output is correct
24 Correct 132 ms 27632 KB Output is correct
25 Correct 132 ms 29688 KB Output is correct
26 Correct 3 ms 29688 KB Output is correct
27 Correct 2 ms 29688 KB Output is correct
28 Correct 164 ms 29688 KB Output is correct
29 Correct 154 ms 29688 KB Output is correct
30 Correct 2 ms 29688 KB Output is correct
31 Correct 2 ms 29688 KB Output is correct
32 Correct 2 ms 29688 KB Output is correct
33 Correct 2 ms 29688 KB Output is correct
34 Correct 2 ms 29688 KB Output is correct
35 Correct 2 ms 29688 KB Output is correct
36 Correct 2 ms 29688 KB Output is correct
37 Correct 2 ms 29688 KB Output is correct
38 Correct 2 ms 29688 KB Output is correct
39 Correct 2 ms 29688 KB Output is correct
40 Correct 2 ms 29688 KB Output is correct
41 Correct 2 ms 29688 KB Output is correct
42 Correct 2 ms 29688 KB Output is correct
43 Correct 157 ms 29688 KB Output is correct
44 Correct 182 ms 29688 KB Output is correct
45 Correct 153 ms 29688 KB Output is correct
46 Correct 143 ms 29688 KB Output is correct
47 Correct 147 ms 29688 KB Output is correct
48 Correct 143 ms 29688 KB Output is correct
49 Correct 146 ms 29688 KB Output is correct
50 Correct 3 ms 29688 KB Output is correct
51 Correct 181 ms 30836 KB Output is correct
52 Correct 137 ms 32240 KB Output is correct
53 Correct 145 ms 33408 KB Output is correct
54 Correct 136 ms 34728 KB Output is correct
55 Correct 2 ms 34728 KB Output is correct
56 Correct 2 ms 34728 KB Output is correct
57 Correct 2 ms 34728 KB Output is correct
58 Correct 2 ms 34728 KB Output is correct
59 Correct 2 ms 34728 KB Output is correct
60 Correct 2 ms 34728 KB Output is correct
61 Correct 2 ms 34728 KB Output is correct
62 Correct 2 ms 34728 KB Output is correct
63 Correct 2 ms 34728 KB Output is correct
64 Correct 2 ms 34728 KB Output is correct
65 Correct 2 ms 34728 KB Output is correct
66 Correct 2 ms 34728 KB Output is correct
67 Correct 164 ms 36068 KB Output is correct
68 Correct 166 ms 37216 KB Output is correct
69 Correct 155 ms 38560 KB Output is correct
70 Correct 163 ms 39732 KB Output is correct
71 Correct 153 ms 41068 KB Output is correct
72 Correct 131 ms 42336 KB Output is correct
73 Correct 150 ms 43576 KB Output is correct
74 Correct 143 ms 45496 KB Output is correct
75 Correct 147 ms 47176 KB Output is correct
76 Correct 146 ms 49012 KB Output is correct
77 Correct 172 ms 50480 KB Output is correct
78 Correct 163 ms 51836 KB Output is correct
79 Correct 168 ms 53204 KB Output is correct
80 Correct 144 ms 54644 KB Output is correct
81 Correct 126 ms 55932 KB Output is correct
82 Correct 146 ms 57500 KB Output is correct
83 Correct 148 ms 58888 KB Output is correct
84 Correct 134 ms 60864 KB Output is correct
85 Correct 150 ms 62768 KB Output is correct
86 Correct 157 ms 64716 KB Output is correct
87 Correct 186 ms 66804 KB Output is correct
88 Correct 181 ms 68612 KB Output is correct
89 Correct 151 ms 70548 KB Output is correct
90 Correct 185 ms 72544 KB Output is correct
91 Correct 175 ms 74428 KB Output is correct
92 Correct 159 ms 76504 KB Output is correct
93 Correct 160 ms 78352 KB Output is correct
94 Correct 169 ms 80324 KB Output is correct
95 Correct 172 ms 82188 KB Output is correct
96 Correct 149 ms 84224 KB Output is correct
97 Correct 161 ms 86052 KB Output is correct
98 Correct 178 ms 88036 KB Output is correct
99 Correct 151 ms 89932 KB Output is correct
100 Correct 163 ms 91868 KB Output is correct
101 Correct 181 ms 93800 KB Output is correct
102 Correct 142 ms 95692 KB Output is correct