oj.uz

Submission #990779

# Submission time Handle Problem Language Result Execution time Memory
990779 2024-05-31T10:35:05 Z AdamGS Distributing Candies (IOI21_candies) C++17
8 / 100
 263 ms 42576 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);
  return min(trmi[2*N-1], c);
  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+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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 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

# Verdict Execution time Memory Grader output
1 Correct 244 ms 38896 KB Output is correct
2 Correct 263 ms 42576 KB Output is correct
3 Correct 238 ms 42576 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Incorrect 2 ms 9308 KB Output isn't correct
3 Halted 0 ms 0 KB -