Submission #95446

#TimeUsernameProblemLanguageResultExecution timeMemory
95446Retro3014방벽 (JOI15_walls)C++17
10 / 100
35 ms1780 KiB
#include <iostream> #include <algorithm> #include <vector> #include <stdio.h> typedef long long ll; using namespace std; int N, M; struct S{ int a, b; }; vector<S> v; vector<int> P; struct STATE{ STATE (int idx, int type, int data) : idx(idx), type(type), data(data) {} int idx; int type; int data; }; void solve1(){ ll ans = 0; int x = v[0].a, y = v[0].b; for(int i=0; i<P.size(); i++){ int now = P[i]; if(y<now){ ans += (ll)now-y; x += now-y; y = now; }else if(x>now){ ans += (ll)x-now; y -= x-now; x = now; } } printf("%lld", ans); } vector<STATE> st; vector<int> len; vector<ll> ans1, ans2, ans; pair<int, int> calc(int x){ int s = 0, e = st.size()-1, m; while(s<e){ m = (s+e)/2+1; if(st[m].idx>=x){ s = m; }else{ e = m-1; } } pair<int, int> ret; if(st[s].type==1){ ret.first = st[s].data; ret.second = st[s].data+len[x]-1; }else{ ret.first = st[s].data-len[x]+1; ret.second = st[s].data; } return ret; } void solve2(){ for(int i=0; i<v.size(); i++){ len.push_back(v[i].b-v[i].a+1); ans.push_back((ll)0); ans1.push_back((ll)0); ans2.push_back((ll)0); }sort(len.begin(), len.end()); st.push_back({len.size()-1, 1, 0}); for(int i=0; i<P.size(); i++){ int now = P[i]; pair<int, int> tmp = calc(0); if(tmp.first<=now && now<=tmp.second) continue; int s = 0, e = len.size()-1, m; while(s<e){ m = (s+e)/2+1; pair<int, int> p = calc(m); //cout<<'*'<<m<<" "<<p.first<<" "<<p.second<<endl; if(p.first<=now && now<=p.second){ e = m-1; }else{ s = m; } } pair<int, int> p = calc(s); if(p.first>now){ STATE add(s, 1, now); int prv = 0; while(1){ STATE out(0, 0, 0); if(!st.empty() && st.back().idx<=add.idx){ out = st.back(); st.pop_back(); }else{ out.idx = add.idx; out.type = st.back().type; out.data = st.back().data; } if(out.type==1){ ans1[out.idx]+=out.data-add.data; if(prv!=0) ans1[prv-1]-=(out.data-add.data); }else{ ans1[out.idx]+=(out.data-add.data+1); ans2[out.idx]++; if(prv!=0){ ans1[prv-1]-=(out.data-add.data+1); ans2[prv-1]--; } } prv = out.idx+1; if(out.idx==add.idx) break; } st.push_back(add);//cout<<add.idx<<" "<<add.data<<" "<<add.type<<endl; }else{ STATE add(s, 2, now); int prv = 0; while(1){ STATE out(0, 0, 0); if(!st.empty() && st.back().idx<=add.idx){ out = st.back(); st.pop_back(); }else{ out.idx = add.idx; out.type = st.back().type; out.data = st.back().data; } if(out.type==2){ ans1[out.idx]+=add.data-out.data; if(prv!=0) ans1[prv-1]-=(add.data-out.data); }else{ ans1[out.idx]+=(add.data-out.data+1); ans2[out.idx]++; if(prv!=0){ ans1[prv-1]-=(add.data-out.data+1); ans2[prv-1]--; } } prv = out.idx+1; if(out.idx==add.idx) break; } st.push_back(add);//cout<<add.idx<<" "<<add.data<<" "<<add.type<<endl; } } for(int i=ans1.size()-2; i>=0; i--){ ans1[i] += ans1[i+1]; ans2[i] += ans2[i+1]; ans[i] = ans1[i] - (ll)len[i] * ans2[i]; }/* for(int i=0; i<ans1.size(); i++){ if(i!=0){ ans1[i] += ans1[i-1]; ans2[i] += ans2[i-1]; } ans[i] = ans1[i] - (ll)len[i] * ans2[i]; }*/ for(int i=0; i<v.size(); i++){ int s = 0, e = len.size()-1, m = 0; while(s<e){ m = (s+e)/2; if(len[m] == (v[i].b-v[i].a+1)){ s = e = m; break; } if(len[m]>(v[i].b-v[i].a+1)){ e = m-1; }else{ s = m+1; } } printf("%lld\n", ans[s]); } } void solve3(){ } int main(){ scanf("%d%d", &N, &M); for(int i=0; i<N; i++){ S tmp; scanf("%d%d", &tmp.a, &tmp.b); v.push_back(tmp); } for(int i=0; i<M; i++){ int x; scanf("%d", &x); P.push_back(x); } if(N==1){ solve1(); }else solve2(); return 0; }

Compilation message (stderr)

walls.cpp: In function 'void solve1()':
walls.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<P.size(); i++){
               ~^~~~~~~~~
walls.cpp: In function 'void solve2()':
walls.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
walls.cpp:73:26: warning: narrowing conversion of '(len.std::vector<int>::size() - 1)' from 'std::vector<int>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
  st.push_back({len.size()-1, 1, 0});
                ~~~~~~~~~~^~
walls.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<P.size(); i++){
               ~^~~~~~~~~
walls.cpp:158:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
walls.cpp: In function 'int main()':
walls.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tmp.a, &tmp.b); v.push_back(tmp);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x); P.push_back(x);
   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...