제출 #1187164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187164		ardasher_2o	나일강 (IOI24_nile)	C++20	컴파일 에러	0 ms	0 KiB

nile

#include<bits/stdc++.h>
#include "nile.h"
#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<long long> W, std::vector<long long> A, std::vector<long long> B, std::vector<long long> 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]});
      if(i==0){
         ms.push_back(vec[i].sc);
      }
      else{
         ms.push_back(ms.back()+vec[i].sc);
      }
   }
   sort(vec.begin(),vec.end());
   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(long long 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(long long i=0;i<ans.size();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;
   }
   return R;
}
// signed main(){
//    long long f,g;
//    cin>>f>>g;
//    vector<long long> w,a,b,e;
//    for(long long i=0;i<f;i++){
//       long long y;
//       cin>>y;
//       w.push_back(y);
//    }
//    for(long long i=0;i<f;i++){
//       long long y;
//       cin>>y;
//       a.push_back(y);
//    }
//    for(long long i=0;i<f;i++){
//       long long y;
//       cin>>y;
//       b.push_back(y);
//    }
//    for(long long i=0;i<g;i++){
//       long long y;
//       cin>>y;
//       e.push_back(y);
//    }
//    vector<long long> ui=calculate_costs(w,a,b,e);
//    for(auto i : ui){
//       cout<<i<<endl;
//    }
// }

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccxPcTl9.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `calculate_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status