제출 #373224

#제출 시각아이디문제언어결과실행 시간메모리
373224ivan_tudor전선 연결 (IOI17_wiring)C++14
0 / 100
1 ms384 KiB
#include "wiring.h" #include<bits/stdc++.h> using namespace std; const int N = 200005; long long aint[4*N]; long long lazy[4*N]; void propag(int nod,int l, int r){ aint[nod] += lazy[nod]; if(l != r){ lazy[2*nod] += lazy[nod]; lazy[2*nod + 1] += lazy[nod]; } lazy[nod] = 0; } long long computemin(long long a, long long b){ if(a == 0 && b== 0) return 0; if(a == 0) return b; if(b == 0) return a; return min(a, b); } void update(int nod,int l, int r,int ul, int ur, long long val){ propag(nod, l, r); if(l > ur || r < ul || ul > ur) return; if(ul <= l && r <= ur){ lazy[nod] += val; propag(nod, l, r); return; } int mid = (l + r)/2; update(2*nod, l, mid, ul, ur, val); update(2*nod + 1, mid+1, r, ul, ur, val); aint[nod] = computemin(aint[2*nod], aint[2*nod + 1]); } long long query(int nod,int l, int r,int ql, int qr){ propag(nod, l, r); if(l > qr || r < ql || aint[nod] == 0 ) return LLONG_MAX; if(ql <= l && r<= qr){ return aint[nod]; } int mid = (l + r)/2; long long ls = query(2*nod, l, mid, ql, qr); long long rs = query(2*nod + 1, mid + 1, r, ql, qr); return min(ls, rs); } long long dp[N]; struct blocks{ int t; int tip; }; blocks v[N]; long long min_total_length(std::vector<int> r, std::vector<int> b) { int cnt = 0; for(int i = 0,j = 0; i < r.size() || j < b.size();){ if(i == r.size()) v[++cnt] = {b[j], 2}, j++; else if(j == b.size()) v[++cnt] = {r[i], 1}, i++; else if(r[i] < b[j]) v[++cnt] = {r[i], 1}, i++; else v[++cnt] = {b[j], 2}, j++; } int n = cnt; vector<int> cur, prev; cur.push_back(1); for(int i=2; i<=n;i++){ if(v[i].tip == v[i -1].tip){ cur.push_back(i); if(prev.empty()) continue; int lstp = prev[prev.size() - 1], frstp = prev[0]; long long adg1 = v[i].t - v[lstp].t; // adaugam pe intervalul unde se modifica si la mijloc => nr de b uri devine mai mare ca nr de rosii int nrb = cur.size(); update(1, 1, n, max(frstp, lstp - nrb + 2),lstp, adg1); long long adg2 = v[i].t - v[lstp + 1].t; update(1, 1, n, frstp, max(frstp, lstp - nrb + 2) - 1, adg2); } else{ swap(cur, prev); cur.clear(); cur.push_back(i); long long scor = 0; for(int j = prev.size() - 1; j >=0; j--){ scor += v[i].t - v[prev[j]].t; long long dpadg = dp[prev[j] - 1]; if(prev.size() == 1){ dpadg = min(dp[prev[j]-1], dp[prev[j]]); } update(1, 1, n, prev[j], prev[j], dpadg + scor); } } int lstp = prev[prev.size() - 1], frstp = prev[0]; dp[i] = query(1, 1, n, frstp, lstp); } return dp[n]; }

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

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0,j = 0; i < r.size() || j < b.size();){
      |                       ~~^~~~~~~~~~
wiring.cpp:58:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0,j = 0; i < r.size() || j < b.size();){
      |                                       ~~^~~~~~~~~~
wiring.cpp:59:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(i == r.size())
      |      ~~^~~~~~~~~~~
wiring.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   else if(j == b.size())
      |           ~~^~~~~~~~~~~
#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...