Submission #118157

#TimeUsernameProblemLanguageResultExecution timeMemory
118157sealnot123Wiring (IOI17_wiring)C++14
13 / 100
152 ms22960 KiB
#include "wiring.h" //#include "grader.cpp" #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 200005; LL seg[2][4*N], dp[N], FF[N], ff[N], BB[N], bb[N], pos[N]; int col[N], last[N], cnt; int n; void add(LL val, int idx, int t, int l = 1, int r = n, int now = 1){ if(l==r){ seg[t][now] = val; return ; } int m = (l+r)>>1; if(idx <= m) add(val, idx, t, l, m, now<<1); else add(val, idx, t, m+1, r, now<<1|1); seg[t][now] = min(seg[t][now<<1], seg[t][now<<1|1]); } LL get(int ll, int rr, int t, int l = 1, int r = n, int now = 1){ if(ll > rr || l > rr || r < ll) return 1e18; if(l >= ll && r <= rr) return seg[t][now]; int m = (l+r)>>1; return min( get(ll, rr, t, l, m, now<<1), get(ll, rr, t, m+1, r, now<<1|1)); } long long min_total_length(vector<int> A, vector<int> B) { n = SZ(A) + SZ(B); int a, c, d, i, j, k, l = 0, r = 0; while(l < SZ(A) && r < SZ(B)){ if(A[l] < B[r]){ pos[++cnt] = A[l++]; }else{ pos[++cnt] = B[r++]; col[cnt] = 1; } } while(l < SZ(A)) pos[++cnt] = A[l++]; while(r < SZ(B)) pos[++cnt] = B[r++], col[cnt] = 1; last[1] = 1; for(i=2; i<=n; i++){ if(col[i] == col[i-1]) last[i] = last[i-1], FF[i] = FF[i-1], ff[i] = ff[i-1]; else last[i] = i; FF[i] += pos[i] - pos[last[i]-1]; ff[i] += pos[i] - pos[last[i]]; } l = n; for(i = n-1; i>0; i--){ if(col[i] != col[i+1]) l = i+1; else BB[i] = BB[i+1], bb[i] = bb[i+1]; BB[i] += pos[l] - pos[i]; bb[i] += pos[l-1] - pos[i]; } for(i = 1; i <= n; i++){ dp[i] = 1e18; // printf("xxxxxx%d %d : %d %lld %lld %lld %lld\n", pos[i], col[i], last[i], FF[i], ff[i], BB[i], bb[i]); if(last[i] != 1){ d = i-last[i]+1; l = last[last[i]-1]; // printf("##%d %d = %lld\n",max(l, last[i]-d), last[i]-1, get(max(l, last[i]-d), last[i]-1, 0)); dp[i] = min(dp[i], get(max(l, last[i]-d), last[i]-1, 0) + FF[i]); dp[i] = min(dp[i], get(l, last[i]-d-1, 1) + ff[i]); } add(dp[i-1] + bb[i], i, 0); add(dp[i-1] + BB[i], i, 1); // printf("i %d : %lld\n", i, dp[i]); } return dp[n]; } /* 4 5 1 2 3 7 0 4 5 9 10 */

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:38:9: warning: unused variable 'a' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
         ^
wiring.cpp:38:12: warning: unused variable 'c' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
            ^
wiring.cpp:38:21: warning: unused variable 'j' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
                     ^
wiring.cpp:38:24: warning: unused variable 'k' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...