제출 #1131450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131450		huutuan	Tower (JOI24_tower)	C++20	38 / 100	2096 ms	17056 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10;
int n, q, d, a, b, f[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> q >> d >> a >> b;
   set<pair<int, int>> block;
   for (int i=1; i<=n; ++i){
      int l, r; cin >> l >> r;
      if (block.size() && block.rbegin()->second+1==l){
         auto p=*block.rbegin();
         block.erase(prev(block.end()));
         p.second=r;
         block.insert(p);
      }else block.emplace(l, r);
   }
   int xmax=1e18;
   block.emplace((int)-1e18, -1);
   for (auto it=next(block.begin()); it!=block.end(); ++it){
      while (it->second-it->first<d-1){
         bool stop=1;
         int pos=it->second+1-d;
         auto it2=block.lower_bound({pos+1, -1});
         if (it2!=block.begin()){
            --it2;
            if (it2->first<=pos && pos<=it2->second){
               auto p=*it;
               it=block.erase(it);
               p.second+=it2->second-pos+1;
               it=block.insert(p).first;
               stop=0;
            }
         }
         if (stop) break;
         auto p=*it;
         while (next(it)!=block.end() && it->second+1>=next(it)->first){
            p.second=max(p.second, next(it)->second);
            block.erase(next(it));
            block.erase(it);
            it=block.insert(p).first;
         }
      }
   }
   for (auto &i:block) if (i.second-i.first>=d-1){
      if (i.second<0) continue;
      xmax=i.first-1;
      break;
   }
   vector<pair<int, int>> can;
   for (auto it=block.begin(); it!=block.end(); ++it){
      can.emplace_back(it->second+1, next(it)==block.end()?(int)1e18:next(it)->first-1);
   }
   while (q--){
      int x; cin >> x;
      auto it=lower_bound(can.begin(), can.end(), make_pair(x+1, -1ll));
      int ans=x>xmax?-1:0;
      if (it!=can.begin()){
         --it;
         if (it->first<=x && x<=it->second);
         else ans=-1;
      }else ans=-1;
      if (ans==-1) cout << ans << '\n';
      else{
         if (a*d<=b){
            while (x){
               if (it->first==0){
                  ans+=a*x;
                  break;
               }
               ans+=a*(x-it->first);
               x=it->first-d;
               while (!(it->first<=x && x<=it->second)) --it;
               ans+=b;
            }
            cout << ans << '\n';
         }else{
            auto it2=lower_bound(can.begin(), can.end(), make_pair(x-d+1, -1ll));
            while (x){
               if (x-it->first>=d*2){
                  int cnt=(x-it->first-d*2)/d;
                  ans+=cnt*b;
                  x-=cnt*d;
               }
               while (it2!=can.begin() && prev(it2)->first>=x-d+1) --it2;
               while (!(it->first<=x && x<=it->second)) --it;
               if (it2!=can.begin() && x>=d){
                  int pos=min(x, prev(it2)->second+d);
                  ans+=a*(x-pos);
                  x=pos-d;
                  ans+=b;
               }else ans+=a*x, x=0;
               while (it2!=can.begin() && prev(it2)->first>=x-d+1) --it2;
               while (!(it->first<=x && x<=it->second)) --it;
            }
            cout << ans << '\n';
         }
      }
   }
   return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 38 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32