제출 #390057

#제출 시각아이디문제언어결과실행 시간메모리
390057alireza_kaviani전선 연결 (IOI17_wiring)C++11
13 / 100
234 ms15228 KiB
#include <bits/stdc++.h> #include "wiring.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; #define sep ' ' #define X first #define Y second #define lc id << 1 #define rc lc | 1 #define all(x) (x).begin() , (x).end() #define SZ(x) int((x).size()) const int MAXN = 2e5 + 10; const int MOD = 1e9 + 7; const ll INF = 1e18; ll dp[MAXN] , seg[2][MAXN << 2]; void modify(int ind , int x , ll val , int id = 1 , int l = 0 , int r = MAXN){ if(r - l == 1){ seg[ind][id] = val; return; } int mid = l + r >> 1; if(x < mid) modify(ind , x , val , lc , l , mid); else modify(ind , x , val , rc , mid , r); seg[ind][id] = min(seg[ind][lc] , seg[ind][rc]); } ll get(int ind , int ql , int qr , int id = 1 , int l = 0 , int r = MAXN){ if(qr <= l || r <= ql) return INF; if(ql <= l && r <= qr) return seg[ind][id]; int mid = l + r >> 1; return min(get(ind , ql , qr , lc , l , mid) , get(ind , ql , qr , rc , mid , r)); } ll min_total_length(vector<int> r, vector<int> b) { vector<pii> compress = {{-1 , 0} , {MOD , 0}}; int n = SZ(r) + SZ(b); for(int i : r) compress.push_back({i , 0}); for(int i : b) compress.push_back({i , 1}); sort(all(compress)); dp[n] = 0; int x = n , y = -1; ll v = 0 , u = 0; // for(int i = 0 ; i < SZ(compress) ; i++){ // cout << i << sep << compress[i].X << sep << compress[i].Y << endl; // } for(int i = n - 1 ; i >= 0 ; i--){ if(y == -1) dp[i] = INF; else{ v += compress[x + 1].X - compress[i + 1].X; u += compress[x].X - compress[i + 1].X; dp[i] = min(get(0 , x + 1 , min(y + 1 , 2 * x - i + 1)) + v , get(1 , 2 * x - i + 1 , y + 1) + u); } // cout << i << sep << dp[i] << endl; if(i > 0 && compress[i].Y != compress[i + 1].Y){ y = x; x = i; v = 0 , u = 0; ll A = 0 , B = 0; for(int j = i + 1 ; j <= y ; j++){ A += compress[j].X - compress[x + 1].X; B += compress[j].X - compress[x].X; modify(0 , j , dp[j] + A); modify(1 , j , dp[j] + B); } continue; } } return dp[0]; }

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'void modify(int, int, ll, int, int, int)':
wiring.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid = l + r >> 1;
      |            ~~^~~
wiring.cpp: In function 'll get(int, int, int, int, int, int)':
wiring.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int mid = l + r >> 1;
      |            ~~^~~
#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...