Submission #1188740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188740		hyakup	Distributing Candies (IOI21_candies)	C++20	0 / 100	701 ms	45620 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<long long, long long>;
const int maxn = 2e5 + 10;

const ll inf = 1e13;

struct Evento{
  int prior, id, val; Evento( int prior, int id, int val ) : prior(prior), id(id), val(val) {}
  bool operator < ( Evento e ){
    return (( prior == e.prior ) ? abs(val) > abs(e.val) : prior < e.prior );
  }
};

class Segment_Tree{
private:
  struct Node{
    pll mini, maxi;
    ll tot;
    Node(){
      mini = pll( inf, 0 );
      maxi = pll( -inf, 0 );
      tot = 0;
    }
    Node( pll val ) : mini(val), maxi(val), tot(val.first) {}

    Node operator + ( Node n ){
      Node resp;
      resp.mini = min( mini, pll( tot + n.mini.first, n.mini.second ) );
      resp.maxi = max( maxi, pll( tot + n.maxi.first, n.maxi.second ) );
      resp.tot = tot + n.tot;
      return resp;
    }
  };
  vector<Node> seg;
  int n;

  void update( int pos, int ini, int fim, int id, int val ){
    if( ini > id || id > fim ) return;
    if( ini == fim ){ seg[pos] = Node( pll( seg[pos].tot + val, ini ) ); return; }
    int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
    update( l, ini, mid, id, val ); update( r, mid + 1, fim, id, val );
    seg[pos] = seg[l] + seg[r];
  }

  Node query( int pos, int ini, int fim, int ki, int kf ){
    if( ki > fim || ini > kf ) return seg[0];
    if( ki <= ini && fim <= kf ) return seg[pos];
    int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
    return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
  }

public:

  void update( int id, int val ){ update( 1, 0, n - 1, id, val ); }

  int query( ll val ){

    int l = (( seg[1].mini.first <= 0 ) ? seg[1].mini.second + 1 : 0 );
    int r = n - 1;

    if( l > r ) return 0;

    while( l < r ){
      int mid = ( l + r + 1 )/2;
      Node x = query( 1, 0, n - 1, mid, n - 1 );
      if( x.mini.first <= -val || x.maxi.first >= val || x.maxi.first - x.mini.first >= val ) l = mid;
      else r = mid - 1;
    }


    Node x = query( 1, 0, n - 1, r, n - 1 );

    if( x.maxi.first >= val )
      return val + query( 1, 0, n - 1, x.maxi.second + 1, n - 1 ).tot;

    return query( 1, 0, n - 1, x.mini.second + 1, n - 1 ).tot;
  }

  Segment_Tree( int n ) : n(n){ seg.resize(4*n); }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v ){
  int n = c.size(), q = l.size();
  vector<Evento> line;
  for( int i = 0; i < n; i++ ) line.push_back( Evento( i, i, 0 ) );
  for( int i = 0; i < q; i++ ){
    line.push_back( Evento( l[i], i, v[i] ) );
    line.push_back( Evento( r[i] + 1, i, -v[i] ) );
  }

  sort( line.begin(), line.end() );

  Segment_Tree seg(q);

  vector<int> resp(n);

  for( auto x : line ){
    if( x.val != 0 ) seg.update( x.id, x.val );
    else resp[x.id] = seg.query(c[x.id]);
  }

  return resp;

}

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