Submission #282922

#TimeUsernameProblemLanguageResultExecution timeMemory
282922arnold518방벽 (JOI15_walls)C++14
10 / 100
3093 ms28112 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; struct Data { int l, r, p; }; int N, M; Data A[MAXN+10]; int B[MAXN+10], col[MAXN+10]; ll ans[MAXN+10]; int main() { scanf("%d%d", &N, &M); for(int i=1; i<=N; i++) { scanf("%d%d", &A[i].l, &A[i].r); A[i].p=i; } for(int i=1; i<=M; i++) scanf("%d", &B[i]); M=unique(B+1, B+M+1)-B-1; vector<int> V; V.push_back(B[1]); for(int i=2; i<M; i++) { if(B[i-1]<B[i] && B[i+1]<B[i]) V.push_back(B[i]); else if(B[i-1]>B[i] && B[i+1]>B[i]) V.push_back(B[i]); } V.push_back(B[M]); for(int i=0; i<V.size(); i++) B[i+1]=V[i]; M=V.size(); sort(A+1, A+N+1, [&](const Data &p, const Data &q) { return p.r-p.l<q.r-q.l; }); multiset<pii> S; set<int> S2; ll sum=0; for(int i=1; i<M; i++) S.insert({abs(B[i+1]-B[i]), i+1}), sum+=abs(B[i+1]-B[i]); for(int i=1; i<=M; i++) S2.insert(i), col[i]=(i+1)%2; for(int i=1; i<=N; i++) { int len=A[i].r-A[i].l; set<int> S3; for(auto it : S) { if(it.first<=len) S3.insert(it.second); else break; } while(!S3.empty()) { int now=*S3.begin(), l, r; auto it=S2.find(now); if(col[now]==1) l=B[*prev(it)], r=B[*prev(it)]+len; else r=B[*prev(it)], l=B[*prev(it)]-len; vector<pii> V; for(; it!=S2.end(); it++) { V.push_back({abs(B[*it]-B[*prev(it)]), *it}); if(!(l<=B[*it] && B[*it]<=r)) break; } if(it==S2.end()) { for(auto jt : V) { if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second); if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second); if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first; } } else if(col[*it]==col[now]) { for(auto jt : V) { if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second); if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second); if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first; } S2.insert(*it); auto pt=S2.find(*it), qt=prev(pt); S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]); } else { auto kt=prev(S2.find(now)); V.push_back({abs(B[*kt]-B[*prev(kt)]), *kt}); for(auto jt : V) { //printf("V %d %d\n", jt.first, jt.second); if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second); if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second); if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first; } S2.insert(*it); auto pt=S2.find(*it), qt=prev(pt); S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]); } S3.erase(now); } //for(auto it : S) printf("%d %d\n", it.first, it.second); //printf("=> %lld %d\n", sum, A[i].p); bool flag=false; int l=A[i].l, r=A[i].r; for(auto it=S2.begin(); it!=S2.end(); it++) { if(B[*it]<l) { ans[A[i].p]+=l-B[*it]; r-=l-B[*it]; l-=l-B[*it]; } else if(r<B[*it]) { ans[A[i].p]+=B[*it]-r; l+=B[*it]-r; r+=B[*it]-r; } //printf("!%d %lld\n", B[*it], ans[A[i].p]); } //printf("\n"); //ans[A[i].p]=sum-(ll)S.size()*len; } for(int i=1; i<=N; i++) printf("%lld\n", ans[i]); }

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<V.size(); i++) B[i+1]=V[i];
      |               ~^~~~~~~~~
walls.cpp:116:8: warning: unused variable 'flag' [-Wunused-variable]
  116 |   bool flag=false;
      |        ^~~~
walls.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d%d", &A[i].l, &A[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=M; i++) scanf("%d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...