Submission #249589

#TimeUsernameProblemLanguageResultExecution timeMemory
249589LittleFlowers__Sky Walking (IOI19_walk)C++17
0 / 100
51 ms25076 KiB
#include <bits/stdc++.h> using namespace std; #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0); #define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a) #define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f, x) memset(f, x, sizeof(f)) #define gg exit(0); const long long INF=1e9+10; const int N=100010; int f[N]; vector<int> val; multiset<int> up[N],dw[N]; void upd_u(int i,int j,int t){ i=lower_bound(all(val),i)-val.begin()+1; for(;i;i-=i&-i){ if(t) dw[i].insert(j); else dw[i].erase(dw[i].find(j)); } } void upd_d(int i,int j,int t){ i=lower_bound(all(val),i)-val.begin()+1; for(;i<=val.size();i+=i&-i){ if(t) up[i].insert(j); else up[i].erase(dw[i].find(j)); } } int que_u(int i){ i=lower_bound(all(val),i)-val.begin()+1; int ret=INF; for(;i<=val.size();i+=i&-i) if(dw[i].size()) ret=min(ret,*dw[i].begin()); return ret; } int que_d(int i){ i=lower_bound(all(val),i)-val.begin()+1; int ret=INF; for(;i;i-=i&-i) if(up[i].size()) ret=min(ret,*dw[i].begin()); return ret; } long long min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){ /// noi toa nha l va r o do cao y /** _________ ________ f_i = f_j + x[l_i] - x[l_j] + abs(y_i-y_j) x[l_i] + y_i + f_j - x[l_j] - y_j */ val=y, val.pb(0), sort(all(val)), val.erase(unique(all(val)),val.end()); vector<ii> q; forinc(i,1,l.size()){ q.push_back({l[i-1],-i}); q.push_back({r[i-1],i}); } q.push_back({0,l.size()+1}); q.push_back({0,-l.size()-1}); sort(all(q)); y.emplace_back(); int ret=INF; forv(i,q){ if(i.se<0){ f[-i.se]=min(x[l[-i.se]]+y[-i.se]+que_d(y[-i.se]),x[l[-i.se]]-y[-i.se]+que_u(y[-i.se])); upd_d(y[-i.se],f[-i.se]-x[l[-i.se]]-y[-i.se],1); upd_u(y[-i.se],f[-i.se]-x[l[-i.se]]+y[-i.se],1); if(r[-i.se]==x.size()-1) ret=min(ret,f[-i.se]+r[-i.se]-l[-i.se]+y[-i.se]); } else{ upd_d(y[i.se],f[i.se]-x[l[i.se]]-y[i.se],0); upd_u(y[i.se],f[i.se]-x[l[i.se]]+y[i.se],0); } } return ret; } /** main(){ #define task "TASK" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); } } */

Compilation message (stderr)

walk.cpp: In function 'void upd_d(int, int, int)':
walk.cpp:35:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i){
          ~^~~~~~~~~~~~
walk.cpp: In function 'int que_u(int)':
walk.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i) if(dw[i].size())
          ~^~~~~~~~~~~~
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:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(r[-i.se]==x.size()-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...