제출 #1126225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126225		ntdaccode	나일강 (IOI24_nile)	C++20	100 / 100	136 ms	22840 KiB

nile

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
typedef pair<ll,ll> ii;
typedef tuple<ll,ll,ll> tp;
const int M=1e5+10;
const int N=1e3+10;
const int mod=1e9+7;
//
ll q,n,res=0;
struct node
{
  ll w,a,b;
}pos[M];
bool cmp (const node &a,const node &b)
{
  return a.w<b.w;
}
ii d[M];
// segment tree
struct segment_tree
{
  ll t[4*M];
  void reset()
  {
    fori(i,1,4*n) t[i]=1e15;
  }
  void upd(int s,int l,int r,int pos,ll val)
  {
    if(l>pos||r<pos) return ;
    if(l==r)
    {
      t[s]=val;
      return ;
    }
    int mid=(l+r)/2;
    upd(s*2,l,mid,pos,val);
    upd(s*2+1,mid+1,r,pos,val);
    t[s]=min(t[s*2],t[s*2+1]);
  }
  ll get(int s,int l,int r,int u,int v)
  {
    if(l>v||r<u) return 1e15;
    if(u<=l&&r<=v) return t[s];
    int mid=(l+r)/2;
    return min(get(s*2,l,mid,u,v),get(s*2+1,mid+1,r,u,v));
  }
} T[2];
// dsu
ll id[M],val[M],sum[M];
int finded(int u)
{
  return id[u]<0 ? u : id[u]=finded(id[u]);
}
void unioned(int u,int v)
{
  //cout << u << " " << v << "sa\n";
  u=finded(u);
  v=finded(v);
  id[u]+=id[v];
  id[v]=u;
  int sz=abs(id[u]);


  res-=val[u];
  res-=val[v];
  if(sz%2) {
      val[u]=sum[u+sz-1]-sum[u-1]+T[u%2].get(1,1,n,u,u+sz-1);
      res+=val[u];
  }
  else{
    val[u]=sum[u+sz-1]-sum[u-1];
    res+=val[u];
  }
}
vector<node> edge;
vector<ii>  odd;
void pre()
{
  fori(i,1,n-1) edge.push_back({pos[i+1].w - pos[i].w,i,i + 1});
  fori(i,1,n-2) odd.push_back({pos[i+2].w - pos[i].w,i + 1});
  sort(edge.begin(),edge.end(),cmp);
  sort(odd.begin(),odd.end());
  fori(i,1,n) {
    id[i] = -1;
    sum[i] = sum[i-1] + pos[i].b;
    val[i] += pos[i].a;
    res += pos[i].a;
  }
  fori(i,0,1) T[i].reset();
  for(int i = 1;i <= n;i += 2) T[1].upd(1,1,n,i,pos[i].a - pos[i].b);// min
  for(int i = 2;i <= n;i += 2) T[0].upd(1,1,n,i,pos[i].a - pos[i].b);

}
ll ret[M];
void solve()
{
  int j=0;
  int e=0;
  fori(i,1,q){
    ll w=d[i].first;
    int idx=d[i].second;
    while(e!=odd.size()&&odd[e].first<=w){
        int idx2=odd[e].second;
        //cout << idx2 << " " << pos[idx2].b << "a\n";
        T[idx2%2==0].upd(1,1,n,idx2,pos[idx2].a-pos[idx2].b);
        int u=finded(idx2);
        int sz=abs(id[u]);
        res-=val[u];
        if(sz%2) {
            val[u]=sum[u+sz-1]-sum[u-1]+T[u%2].get(1,1,n,u,u+sz-1) ;
            res+=val[u];
        }
        else {
            val[u]=sum[u+sz-1]-sum[u-1] ;
            res+=val[u];
        }
        e++;
    }
    while(j!=edge.size()&&edge[j].w<=w){
      unioned(edge[j].a,edge[j].b);
      j++;
    }
  //  cout << odd[e].first << " " << w << " " << edge[j].w << "\n";
    ret[idx]=res;
  }
  //fori(i,1,q) cout << ret[i] << "\n";
}


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
  n=W.size();
  fori(i,1,n) {
    pos[i].w=W[i - 1];
    pos[i].a=A[i - 1];
    pos[i].b=B[i - 1];
  }
  sort(pos + 1, pos + n + 1, cmp);
  q = E.size();
  fori(i,1,q) {
    d[i].first = E[i - 1];
    d[i].second = i;
  }
  sort(d+1,d+q+1);
    pre();
    solve();
    vector<long long > R;
    fori(i,1,q) R.push_back(ret[i]);
    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