제출 #932357

#제출 시각아이디문제언어결과실행 시간메모리
932357beepbeepsheepSky Walking (IOI19_walk)C++17
0 / 100
77 ms21580 KiB
#include "walk.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define iiii tuple<ll,ll,ll,ll> const ll maxn=1e5+5; const ll inf=1e15; struct node{ ll s,e,m,val; node *l,*r; node(ll _s, ll _e){ s=_s,e=_e,m=(s+e)>>1,val=inf; if (s!=e) l=new node(s,m),r=new node(m+1,e); } void upd(ll x, ll v){ if (s==e){ val=v; return; } if (x>m) r->upd(x,v); else l->upd(x,v); val=min(l->val,r->val); } ll query(ll x, ll y){ if (x<=s && e<=y) return val; if (x>m) return r->query(x,y); if (y<=m) return l->query(x,y); return min(l->query(x,y),r->query(x,y)); } }*small, *big; vector<iiii> bridges; bool cmp(iiii a, iiii b){ if (get<2>(a)==get<2>(b)) return get<3>(a)<get<3>(b); return get<2>(a)<get<2>(b); } long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { ll n=x.size(),m=l.size(); assert(s==0 && g==n-1); small=new node(1,n); big=new node(1,n); for (int i=0;i<m;i++) bridges.emplace_back(l[i],r[i],y[i],i); sort(bridges.begin(),bridges.end(),cmp); //sorted by height vector<iiii> queries; //time, where to toggle, original height, off/on for (int i=0;i<m;i++){ ll a,b,c,d; tie(a,b,c,d)=bridges[i]; queries.emplace_back(a,i+1,c,1); queries.emplace_back(b,i+1,c,0); } queries.emplace_back(1,0,0,0); sort(queries.begin(),queries.end()); ll ptr=0; small=new node(0,m+5),big=new node(0,m+5); small->upd(0,0); for (int i=0;i<n-1;i++){ while (ptr!=queries.size() && get<0>(queries[ptr])<=i){ ll a,b,c,d; tie(a,b,c,d)=queries[ptr]; if (d==1){ ll lo=small->query(0,b-1)+c; ll hi=big->query(b+1,m+5)-c; ll res=min(lo,hi); small->upd(b,res-c); //get dominated big->upd(b,res+c); //dominated } else{ small->upd(b,inf); big->upd(b,inf); //reset to sentinels } ptr++; } } ll ans=big->query(0,m+5); //0 is under everything return ans+x.back()-x.front(); }

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

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:56:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while (ptr!=queries.size() && get<0>(queries[ptr])<=i){
      |          ~~~^~~~~~~~~~~~~~~~
#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...