Submission #99627

#	Time	Username	Problem	Language	Result	Execution time	Memory
99627		andremfq	Teams (IOI15_teams)	C++17	100 / 100	1808 ms	141568 KiB

teams

//codigo Yan
#include <bits/stdc++.h>

#define ff first
#define ss second
#define MAX 500010
#define OO 1000000010

using namespace std;
typedef pair<int,int> pii;

class PersistentSegTree
{
  public:

    void build(int i)
    {
      e.push_back(e[i]);
      d.push_back(d[i]);
      s.push_back(s[i]);
    }

    int update(int id, int ini, int fim, int i)
    {
      int novo = ++node_cur;

      build(id);

      if(ini == fim)
      {
        s[novo]++;
        return novo;
      }

      int m = (ini + fim)/2;

      if(i <= m)
      {
        int aux = update(e[novo] , ini , m , i);
        e[novo] = aux;
      }
      else
      {
        int aux = update(d[novo] , m + 1 , fim , i);
        d[novo] = aux;
      }

      s[novo] = s[e[novo]] + s[d[novo]];

      return novo;
    }

    int query(int id , int ini , int fim , int i, int j)
    {
      if(id == 0 || ini > j || fim < i) return 0;

      if(i <= ini && fim <= j) return s[id];

      int m = (ini + fim)/2;

      return query(e[id] , ini , m , i , j) + query(d[id] , m + 1 , fim , i , j);
    }

    int bs(int r1, int r2 , int ini , int fim , int v)
    {
      if(ini == fim) return ini;

      int b = s[e[r2]] - s[e[r1]];
      int m = (ini + fim)/2;

      if(b >= v) return bs(e[r1] , e[r2] , ini , m , v);
      return bs(d[r1] , d[r2] , m + 1 , fim , v - b);
    }

    PersistentSegTree()
    {
      e.push_back(0); e.push_back(0);
      d.push_back(0); d.push_back(0);
      s.push_back(0); s.push_back(0);
    }

  private:
    vector<int> e, d;
    vector<int> s;

    int node_cur = 1;
} SEG;

int n;
int root[MAX];

pii points[MAX];

int rectangle_sum(int x1, int x2, int y1, int y2)
{
  int s1 = SEG.query(root[x2] , 0 , n , y1 , y2);
  int s2 = SEG.query(root[x1 - 1] , 0 , n , y1 , y2);

  return s1 - s2;
}

class bars
{
  public:
    int l, r, h;
    int corner;

    bars(int ll, int rr, int hh, int cc)
    {
      l = ll;
      r = rr;
      h = hh;
      corner = cc;
    }
};

class pilha
{
  public:

    bool push(int i, int h)
    {
      bars k(i , i , h , 0);

      while(h >= p.back().h)
      {
        k.l = p.back().l;
        p.pop_back();
      }

      int s = i;

      while(!p.empty())
      {
        int ll = p.back().l;
        int lr = p.back().r;
        int lh = p.back().h;
        int lc = p.back().corner;

        int rs = rectangle_sum(lr + 1 , k.r , k.h + 1 , lh);

        if(rs > s)
        {
          int nh = SEG.bs(root[lr] , root[k.r] , 0 , n , s + rectangle_sum(lr + 1 , k.r , 0 , k.h));

          int tot = rectangle_sum(lr + 1 , k.r , k.h + 1 , nh);

          k.h = nh;
          k.l = lr + 1;
          k.corner = tot - s;

          p.push_back(k);

          return true;
        }

        k.l = ll;
        k.h = lh;
        p.pop_back();

        if(rs <= s && s <= rs + lc)
        {
          k.corner = lc - (s - rs);

          p.push_back(k);

          return true;
        }

        s -= rs + lc;
      }

      return false;
    }

    void clear()
    {
      p.clear();

      bars k(-OO , 0 , OO , 0);
      p.push_back(k);
    }

    pilha()
    {
      bars k(-OO , 0 , OO , 0);
      p.push_back(k);
    }

  private:
    vector<bars> p;
};

void init(int N, int A[], int B[])
{
  n = N;

  for(int g = 0 ; g < n ; g++) points[g].ff = A[g];
  for(int g = 0 ; g < n ; g++) points[g].ss = B[g];

  sort(points , points + n);

  int i = 0;
  root[0] = 1;

  for(int g = 1 ; g <= n ; g++)
  {
    root[g] = root[g - 1];

    while(i < n && points[i].ff == g)
    {
      int aux = SEG.update(root[g] , 0 , n , points[i].ss);
      root[g] = aux;

      i++;
    }
  }
}

int can(int M, int K[])
{
  sort(K , K + M);

  bool error = true;

  pilha s;

  for(int g = 0 ; g < M && error ; g++) error = error && s.push(K[g] , K[g] - 1);

  return (error) ? 1 : 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23