Submission #110498

#	Time	Username	Problem	Language	Result	Execution time	Memory
110498		shoemakerjo	Cake (CEOI14_cake)	C++14	51.67 / 100	2059 ms	77344 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int maxn = 250010;
const int maxq = 500010;
#define LEFT 0
#define RIGHT 1
#define pii pair<int, int>
int n, q;
int a;

map<int, int> mval; //mamp from index to value
int svals[maxn];

struct node {

  node *ch[2];
  int indo; //either negative index or query time thing
  int we; //the random weight
  node *par;

  node(int ii) :
    indo(ii) {
      we = rand() % 1000000;
      ch[0] = ch[1] = NULL;
      par = NULL;
    }

  void setChild(int dir, node *c) {
    ch[dir] = c;
    // cout << this->indo << " :: " << c->indo << endl;
    if (c != NULL) {
      c->par = this;
    }
  }

  int getDirection() {
    if (par == NULL) return -1;
    if (this == par->ch[LEFT]) return LEFT;
    if (this == par->ch[RIGHT]) return RIGHT;
    return -1;
  }

  bool isroot() {
    return !par || (par->ch[LEFT] != this &&
      par->ch[RIGHT] != this);
  }

  void rotateUp() {
    int dir = getDirection();
    node *p = par;
    if (!p->isroot()) {
      p->par->ch[p->getDirection()] = this;
    }
    par = p->par;
    node *pMid = ch[!dir];
    p->setChild(dir, pMid);
    setChild(!dir, p);
  }

};

node *cnodes[maxn]; //current nodes

node *root = NULL;

string tp[maxq];
int qv[maxq][2];


vector<int> inorder;

int seg[maxn*4]; //we want to store a maximum seg tree

void update(int spot, int val, int ss = 1, int se = n, int si = 0) {
  if (spot > se || spot < ss || ss > se) return;
  if (ss == se) {
    seg[si] = val;
    return;
  }
  int mid = (ss+se)/2;
  if (spot <= mid) {
    update(spot, val, ss, mid, si*2+1);
  }
  else update(spot, val, mid+1, se, si*2+2);

  seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

int query(int qs, int qe, int ss = 1, int se = n, int si = 0) {
  if (qs > qe || ss > se || qs > se || qe < ss) return 0;
  if (qs <= ss && se <= qe) return seg[si];

  int mid = (ss+se)/2;
  return max(query(qs, qe, ss, mid, si*2+1),
    query(qs, qe, mid+1, se, si*2+2));
}

void buildtree(int ss = 1, int se = n, int si = 0) {
  if (ss == se) {
    // cout << " here " << ss << " : " << mval[0-ss] << endl;
    seg[si] = mval[0-ss];
    return;
  }
  int mid = (ss+se)/2;
  buildtree(ss, mid, si*2+1);
  buildtree(mid+1, se, si*2+2);
  seg[si] = max(seg[si*2+1], seg[si*2+2]);
}

vector<pii> befa;
vector<pii> afta;

void dfs(node *cur) {

  // cout << "at: " << cur->indo << endl;

  if (cur->ch[LEFT]) {
    dfs(cur->ch[LEFT]);
  }
  inorder.push_back(cur->indo);
  if (cur->ch[RIGHT]) {
    dfs(cur->ch[RIGHT]);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  srand(time(NULL));
  cin >> n >> a;

  vector<pii> stuff;

  for (int i = 1; i <= n; i++) {
    cin >> svals[i];
    stuff.push_back(pii(svals[i], i));
  }
  cin >> q;

  sort(stuff.begin(), stuff.end());
  reverse(stuff.begin(), stuff.end());

  for (pii vp : stuff) {
    int ind = vp.second;
    node *cur = new node(0-ind);
    cnodes[ind] = cur;
    if (root == NULL)  {
      root = cur;
      continue;
    }
    //insert me to be the smallest guy present
    node *tmp = root;
    while (tmp->ch[LEFT] != NULL) {
      tmp = tmp->ch[LEFT];
    }
    tmp->setChild(LEFT, cur);
    //now we need to rotate cur up a bunch
    while (!cur->isroot() &&
      cur->we > cur->par->we) {
        cur->rotateUp();
    }
    if (cur->isroot()) {
      root = cur;
    }
  }

  //store the ten greatest values at any time
  vector<int> tg;
  for (int i = 0; i < 10 && i < stuff.size(); i++) {
    tg.push_back(stuff[i].second);
  }

  for (int i = 0; i < q; i++) {

    // cout << " at start of " << i << " root is: " << root->indo << endl;

    cin >> tp[i];
    if (tp[i] == "E") {
      cin >> qv[i][0] >> qv[i][1];
      int ind = qv[i][0];
      int ec = qv[i][1];
      for (int i = 0; i < tg.size(); i++) {
        if (tg[i] == ind) {
          tg.erase(tg.begin() + i);
        }
      }
      tg.insert(tg.begin() + ec-1, ind);
      node *cur = new node(i);
      cnodes[ind] = cur;
      if (ec == 1) {
        //insert this to be the biggest value we have
        node *tmp = root;
        while (tmp->ch[RIGHT] != NULL) {
          tmp = tmp->ch[RIGHT];
        }
        tmp->setChild(RIGHT, cur);
      }
      else {
        int aft = tg[ec-2];
        //want to be right below this guy
        node *tmp = cnodes[aft];
        // cout << "THIS: " << tmp->indo << endl;
        if (tmp->ch[LEFT] == NULL) {
          tmp->setChild(LEFT, cur);
        }
        else {
          tmp = tmp->ch[LEFT];
          while (tmp->ch[RIGHT] != NULL) {
            tmp = tmp->ch[RIGHT];
          }
          tmp->setChild(RIGHT, cur);
        }
      }
      while (!cur->isroot() &&
        cur->we > cur->par->we) {
          cur->rotateUp();
      }
      if (cur->isroot()) {
        root = cur;
      }
    }
    else {
      cin >> qv[i][0];
      //do not really want to do anything
    }


    // cout << "done with index: " << i << endl;
  }

  // vector<int> find;

  tg.clear();
  for (int i = 0; i < 10 && i < stuff.size(); i++) {
    tg.push_back(stuff[i].second);
  }

  dfs(root);
  // cout << "inorder: ";
  for (int i = 0; i < inorder.size(); i++) {
    int v = inorder[i];
    // cout << v << " ";
    mval[v] = i+1;
  }
  // cout << endl;

  buildtree();

  // cout << "START: " << query(1, n) << endl;
  //now we must process the queries

  for (int i = a-1; i >= 1; i--) {
    if (befa.size() && befa.back().first >= mval[0-i]) {
      continue;
    }
    befa.push_back(pii(mval[0-i], i));
  }

  befa.push_back(pii(10000000, 0));

  for (int i = a+1; i <= n; i++) {
    if (afta.size() && afta.back().first >= mval[0-i]) {
      continue;
    }
    afta.push_back(pii(mval[0-i], i));
  }
  afta.push_back(pii(10000000, n+1));

  for (int ii = 0; ii < q; ii++) {
    if (tp[ii] == "E") {
      int mv = mval[ii];
      int cind = qv[ii][0];
      update(cind, mv);
      if (cind < a) {
        //update befa
        for (int i = befa.size()-1; i >= 0; i--) {
          if (befa[i].second > cind) {
            if (befa[i].first < mv) {
              befa.insert(befa.begin() + i+1, pii(mv, cind));
            }
            break; //do not want to do this
          }
          if (befa[i].first <= mv) {
            befa.erase(befa.begin() + i);
          }
          if (i == 0) {
            befa.insert(befa.begin() + 0, pii(mv, cind));
          }
        }

      }
      if (cind > a) {
        //update afta
        for (int i = afta.size()-1; i >= 0; i--) {
          if (afta[i].second < cind) {
            if (afta[i].first < mv) {
              afta.insert(afta.begin() + i+1, pii(mv, cind));
            }
            break; //do not want to do this
          }
          if (afta[i].first <= mv) {
            afta.erase(afta.begin() + i);
          }
          if (i == 0) {
            afta.insert(afta.begin() + 0, pii(mv, cind));
          }
        }
      }
    }
    else {
      int mq = qv[ii][0];
      if (mq == a) {
        cout << 0 << '\n';
      }
      else if (mq < a) {
        int bg = query(mq, a-1);
        //binary search to find first ind greater than me

        int lo = 0, hi = afta.size()-1;

        while (lo < hi) {
          int mid = (lo + hi)/2;
          if (afta[mid].first > bg) {
            hi = mid;
          }
          else lo = mid+1;
        }
        // if (ii == 0) cout << "  value : " << bg << endl;
        // if (ii == 0) cout << lo << " : " << befa[lo].second << endl;
        int res = afta[lo].second - mq - 1;
        cout << res << '\n';
      }
      else if (mq > a) {
        int bg = query(a+1, mq);
        int lo = 0, hi = befa.size()-1;

        while (lo < hi) {
          int mid = (lo + hi)/2;
          if (befa[mid].first > bg) {
            hi = mid;
          }
          else lo = mid+1;
        }
        int res = mq - befa[lo].second - 1;
        cout << res << '\n';
      }
    }
  }
  cout.flush();

}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:171:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < 10 && i < stuff.size(); i++) {
                             ~~^~~~~~~~~~~~~~
cake.cpp:184:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < tg.size(); i++) {
                       ~~^~~~~~~~~~~
cake.cpp:236:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < 10 && i < stuff.size(); i++) {
                             ~~^~~~~~~~~~~~~~
cake.cpp:242:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < inorder.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 16.666667 / 50