Submission #990787

#	Time	Username	Problem	Language	Result	Execution time	Memory
990787		AdamGS	사탕 분배 (IOI21_candies)	C++17	100 / 100	260 ms	45396 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll trma[4*LIM], trmi[4*LIM], lazy[4*LIM], N=1, n, q;
void spl(int v) {
  trma[2*v]+=lazy[v];
  trma[2*v+1]+=lazy[v];
  trmi[2*v]+=lazy[v];
  trmi[2*v+1]+=lazy[v];
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, ll x) {
  if(b<l || r<a) return;
  if(a<=l && r<=b) {
    trma[v]+=x;
    trmi[v]+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  trma[v]=max(trma[2*v], trma[2*v+1]);
  trmi[v]=min(trmi[2*v], trmi[2*v+1]);
}
ll zejdz(ll c) {
  ll v=1, aktma=-INF, aktmi=INF;
  while(v<N) {
    if(lazy[v]) spl(v);
    if(min(aktmi, trmi[2*v+1])+c>=max(aktma, trma[2*v+1])) {
      aktmi=min(aktmi, trmi[2*v+1]);
      aktma=max(aktma, trma[2*v+1]);
      v=2*v;
    } else v=2*v+1;
  }
  for(int i=1; i<N; i=2*i+1) spl(i);
  aktma=max(aktma, trma[v]);
  aktmi=min(aktmi, trmi[v]);
  if(trma[v]==aktma) {
    return trmi[2*N-1]-aktmi;
  }
  return c-(aktma-trmi[2*N-1]);
}
vector<int>distribute_candies(vector<int>c, vector<int>l, vector<int>r, vector<int>v) {
  n=c.size(); q=l.size();
  while(N<q+3) N*=2;
  upd(1, 0, N-1, 0, 0, -INF);
  upd(1, 0, N-1, 1, 1, INF);
  upd(1, 0, N-1, 2, 2, 0);
  rep(i, q) {
    V[l[i]].pb({v[i], i+3});
    V[r[i]+1].pb({-v[i], i+3});
  }
  vector<int>ans(n);
  rep(i, n) {
    for(auto j : V[i]) upd(1, 0, N-1, j.nd, N-1, j.st);
    ans[i]=zejdz(c[i]);
  }
  return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33