oj.uz

Submission #110498

# Submission time Handle Problem Language Result Execution time Memory
110498 2019-05-11T04:04:52 Z shoemakerjo Cake (CEOI14_cake) C++14
51.6667 / 100
 2000 ms 77344 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16128 KB Output is correct
2 Correct 17 ms 16000 KB Output is correct
3 Correct 18 ms 16128 KB Output is correct
4 Correct 22 ms 16504 KB Output is correct
5 Correct 48 ms 18104 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 29844 KB Time limit exceeded
2 Execution timed out 2059 ms 45972 KB Time limit exceeded
3 Execution timed out 2016 ms 30300 KB Time limit exceeded
4 Correct 567 ms 74724 KB Output is correct
5 Execution timed out 2049 ms 27000 KB Time limit exceeded
6 Execution timed out 2031 ms 29652 KB Time limit exceeded
7 Execution timed out 2058 ms 29612 KB Time limit exceeded
8 Correct 564 ms 77344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 31552 KB Output is correct
2 Correct 155 ms 31452 KB Output is correct
3 Correct 140 ms 31472 KB Output is correct
4 Correct 20 ms 16000 KB Output is correct
5 Correct 578 ms 51432 KB Output is correct
6 Correct 582 ms 51688 KB Output is correct
7 Correct 268 ms 51176 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 19832 KB Output is correct
2 Correct 164 ms 20208 KB Output is correct
3 Correct 815 ms 28212 KB Output is correct
4 Correct 773 ms 28048 KB Output is correct
5 Correct 314 ms 26224 KB Output is correct
6 Execution timed out 2052 ms 26524 KB Time limit exceeded
7 Correct 1149 ms 30988 KB Output is correct
8 Execution timed out 2040 ms 31556 KB Time limit exceeded
9 Execution timed out 2054 ms 38760 KB Time limit exceeded
10 Correct 930 ms 49512 KB Output is correct
11 Execution timed out 2051 ms 25984 KB Time limit exceeded
12 Execution timed out 2056 ms 36072 KB Time limit exceeded
13 Execution timed out 2051 ms 44724 KB Time limit exceeded