제출 #1187240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187240		ardasher_2o	Nile (IOI24_nile)	C++20	100 / 100	141 ms	28328 KiB

nile

#include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <utility>
#include <cmath>
#define fr first
#define sc second
using namespace std;
const long long MAX = 1e5+5;
const long long MOD = 998244353, P = 29;
const long long MIX = 1e15+7;
struct tree{
   long long sz=1;
   vector<long long> tre[2];
   void full(long long o){
      while(sz<o){
         sz*=2;
      }
      tre[0].assign(sz*2-1,-MIX);
      tre[1].assign(sz*2-1,-MIX);
   }
   void add(long long ps, long long v, long long z){
      add(ps, v, z, 0, sz, 0);
   }
   void add(long long ps, long long v, long long z, long long lr, long long rl, long long x){
      if(rl-lr==1){
         tre[z][x]=v;
         return;
      }
      long long mid=(rl+lr)/2;
      if(mid<=ps){
         add(ps, v, z, mid, rl, x*2+2);
      }
      else{
         add(ps, v, z, lr, mid, x*2+1);
      }
      tre[z][x]=max(tre[z][x*2+1],tre[z][x*2+2]);
   }
   long long take(long long L, long long R, long long z){
      return take(L, R, z, 0, sz-1, 0);
   }
   long long take(long long L, long long R, long long z, long long lr, long long rl, long long x){
      if(L>rl || lr>R){
         return -MIX;
      }
      if(L<=lr && rl<=R){
         return tre[z][x];
      }
      long long mid=(rl+lr)/2;
      return max(take(L, R, z, mid+(rl+lr)%2, rl, x*2+2), take(L, R, z, lr, mid, x*2+1));
   }
};
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
   tree tr;
   long long q = E.size();
   long long n = W.size(),sum=0;
   tr.full(n);
   for(auto i : A){
      sum+=i;
   }
   vector<pair<long long,long long>> ans;
   vector<long long> R(q, 0),ms;
   vector<pair<long long,long long>> vec;
   for(long long i=0;i<n;i++){
      vec.push_back({W[i],B[i]-A[i]});
   }
   sort(vec.begin(),vec.end());
   for(int i=0;i<n;i++){
    if(i==0){
         ms.push_back(vec[i].sc);
      }
      else{
         ms.push_back(ms.back()+vec[i].sc);
      }
   }
   vector<pair<long long,pair<long long,long long>>> color;
   vector<long long> price(n,0);
   for(long long i=0;i<n;i++) color.push_back({i,{i,i}});
   set<pair<long long,pair<long long,long long>>> dif;
   for(long long i=1;i<n;i++){
      dif.insert({vec[i].fr-vec[i-1].fr,{i-1,1}});
   }
   for(long long i=1;i<n-1;i++){
      dif.insert({vec[i+1].fr-vec[i-1].fr,{i,2}});
   }
   for(long long i=0;i<n;i+=2){
      tr.add(i, vec[i].sc, 0);
   }
   for(long long i=1;i<n;i+=2){
      tr.add(i, vec[i].sc, 1);
   }
   ans.push_back({-1,sum});
   while(!dif.empty()){
      pair<long long,pair<long long,long long>> pr=*dif.begin();
      dif.erase(dif.begin());
      if(pr.sc.sc==1){
         long long clr1 = color[pr.sc.fr].fr, clr2 = color[pr.sc.fr + 1].fr;
         if(color[clr1].sc.sc-color[clr1].sc.fr>color[clr2].sc.sc-color[clr2].sc.fr){
            color[clr1].sc.sc=color[clr2].sc.sc;
            for(int i=color[clr2].sc.fr;i<=color[clr2].sc.sc;i++){
               color[i].fr=clr1;
            }
            sum-=price[clr1]+price[clr2];
            if((color[clr1].sc.sc-color[clr1].sc.fr)%2==0){
                
            if(color[clr1].sc.fr==0){
               price[clr1]=ms[color[clr1].sc.sc]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
            }
            else{
               price[clr1]=ms[color[clr1].sc.sc]-ms[color[clr1].sc.fr-1]-tr.take(color[clr1].sc.fr,color[clr1].sc.sc,color[clr1].sc.fr%2);
            }
            sum+=price[clr1];}
            else{
               if(color[clr1].sc.fr==0){
               price[clr1]=ms[color[clr1].sc.sc];
            }
            else{
               price[clr1]=ms[color[clr1].sc.sc]-ms[color[clr1].sc.fr-1];
            }
            sum+=price[clr1];
            }
         }
         else{
            color[clr2].sc.fr=color[clr1].sc.fr;
            for(long long i=color[clr1].sc.fr;i<=color[clr1].sc.sc;i++){
               color[i].fr=clr2;
            }
            sum-=price[clr1]+price[clr2];
            if((color[clr2].sc.sc-color[clr2].sc.fr)%2==0){
            if(color[clr2].sc.fr==0){
               price[clr2]=ms[color[clr2].sc.sc]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
            }
            else{
               price[clr2]=ms[color[clr2].sc.sc]-ms[color[clr2].sc.fr-1]-tr.take(color[clr2].sc.fr,color[clr2].sc.sc,color[clr2].sc.fr%2);
            }
            sum+=price[clr2];
            }
            else{
               if(color[clr2].sc.fr==0){
               price[clr2]=ms[color[clr2].sc.sc];
            }
            else{
               price[clr2]=ms[color[clr2].sc.sc]-ms[color[clr2].sc.fr-1];
            }
            sum+=price[clr2];
            }
         }
      }
      else{
         tr.add(pr.sc.fr, vec[pr.sc.fr].sc, (pr.sc.fr+1)%2);
         long long clr = color[pr.sc.fr].fr;
         sum-=price[clr];
         if((color[clr].sc.sc-color[clr].sc.fr)%2==0){
         if(color[clr].sc.fr==0){
               price[clr]=ms[color[clr].sc.sc]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
            }
            else{
               price[clr]=ms[color[clr].sc.sc]-ms[color[clr].sc.fr-1]-tr.take(color[clr].sc.fr,color[clr].sc.sc,color[clr].sc.fr%2);
            }
         }
         sum+=price[clr];
      }
      if(ans.back().fr==pr.fr){
         ans.pop_back();
      }
      ans.push_back({pr.fr,sum});
   }
   for(int i=0;i<q;i++){
      long long lr=0,rl=ans.size();
      while(rl-lr!=1){
         long long mid=(rl+lr)/2;
         if(ans[mid].fr<=E[i]){
            lr=mid;
         }
         else{
            rl=mid;
         }
      }
      R[i]=ans[lr].sc;
   }
   // for(auto i : ans){
   //  cout<<i.fr<<' '<<i.sc<<endl;
   // }
   return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18