oj.uz

답안 #990782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990782 2024-05-31T10:41:29 Z AdamGS 사탕 분배 (IOI21_candies) C++17
8 / 100
 259 ms 41372 KB 
#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) {
    if(trma[v]==INF) return min(trmi[2*N-1], c);
    return trmi[2*N-1]-aktmi;
  }
  if(trmi[v]==-INF) return min(trmi[2*N-1], c);
  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+2) N*=2;
  upd(1, 0, N-1, 0, 0, INF);
  upd(1, 0, N-1, 1, 1, -INF);
  rep(i, q) {
    V[l[i]].pb({v[i], i+2});
    V[r[i]+1].pb({-v[i], i+2});
  }
  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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Incorrect 2 ms 9308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 41372 KB Output is correct
2 Correct 259 ms 40364 KB Output is correct
3 Correct 247 ms 41040 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Incorrect 69 ms 35668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Incorrect 2 ms 9308 KB Output isn't correct
3 Halted 0 ms 0 KB -