Submission #1235980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235980		Malix	Nile (IOI24_nile)	C++20	38 / 100	84 ms	16700 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,ll,ll> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vector<ll> od,ev,val,tw;
vi p,s;
vector<pi> r;
vector<ti> a;
ll c=0;

int parent(int x){
  if(p[x]==x)return x;
  return p[x]=parent(p[x]);
}

void merge(int x,int y){
  x=parent(x);
  y=parent(y);
  if(x==y)return;
  if(s[x]<s[y])swap(x,y);
  s[x]+=s[y];
  c-=(val[x]+val[y]);
  p[y]=x;
  od[x]=min(od[x],od[y]);
  ev[x]=min(ev[x],ev[y]);
  tw[x]=min(tw[x],tw[y]);
  r[x]={min(r[x].F,r[y].F),max(r[x].S,r[y].S)};
  val[x]=get<2>(a[r[x].S])-(r[x].F-1>=0?get<2>(a[r[x].F-1]):0);
  if(s[x]%2==1){
    if(r[x].F%2==0)val[x]+=min(tw[x],ev[x]);
    else val[x]+=min(tw[x],od[x]);
  }
  c+=val[x];
}


std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
  int m=E.size();
  vector<pair<ll,int>> arr(m);
  REP(i,0,m)arr[i]={E[i],i};
  sort(all(arr));
  int n=W.size();
  a.resize(n);
  REP(i,0,n)a[i]={W[i],A[i],B[i]};
  sort(all(a));
  priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq,pq2;
  REP(i,0,n-1)pq.push({get<0>(a[i+1])-get<0>(a[i]),i});
  REP(i,0,n-2)pq2.push({get<0>(a[i+2])-get<0>(a[i]),i+1});
  p.resize(n);s.resize(n,1);r.resize(n);val.resize(n);tw.resize(n,INF);
  REP(i,0,n){
    p[i]=i;
    r[i]={i,i};
    val[i]=get<1>(a[i]);
  }
  od.resize(n,INF),ev.resize(n,INF);
  vector<ll> tmp(n);
  REP(i,0,n){
    if(i%2==0)ev[i]=get<1>(a[i])-get<2>(a[i]);
    else od[i]=get<1>(a[i])-get<2>(a[i]);
    tmp[i]=get<1>(a[i])-get<2>(a[i]);
  }
  REP(i,0,n)c+=(ll)A[i];
  vector<ll> ans(m,0);
  REP(i,1,n)get<2>(a[i])+=get<2>(a[i-1]);
  REP(i,0,m){
    ll D=arr[i].F;
    while(!pq2.empty()&&pq2.top().F<=D){
      auto [x,y]=pq2.top();
      pq2.pop();
      tw[parent(y)]=min(tw[parent(y)],tmp[y]);
    }
    while(!pq.empty()&&pq.top().F<=D){
      auto [x,y]=pq.top();
      pq.pop();
      merge(y,y+1);
    }
    ans[arr[i].S]=c;
  }
  return ans;
}

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