oj.uz

답안 #110500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110500 2019-05-11T04:08:41 Z shoemakerjo 케이크 (CEOI14_cake) C++14
51.6667 / 100
 2000 ms 72136 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;

mt19937 mt_rand(time(NULL));

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 = mt_rand() % 1000000000;
      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:175:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < 10 && i < stuff.size(); i++) {
                             ~~^~~~~~~~~~~~~~
cake.cpp:188:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < tg.size(); i++) {
                       ~~^~~~~~~~~~~
cake.cpp:240:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < 10 && i < stuff.size(); i++) {
                             ~~^~~~~~~~~~~~~~
cake.cpp:246: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

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 15972 KB Output is correct
2 Correct 17 ms 16128 KB Output is correct
3 Correct 16 ms 16000 KB Output is correct
4 Correct 22 ms 16512 KB Output is correct
5 Correct 42 ms 18116 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2058 ms 29792 KB Time limit exceeded
2 Execution timed out 2064 ms 42520 KB Time limit exceeded
3 Execution timed out 2037 ms 30352 KB Time limit exceeded
4 Correct 500 ms 70212 KB Output is correct
5 Execution timed out 2028 ms 26320 KB Time limit exceeded
6 Execution timed out 2062 ms 28632 KB Time limit exceeded
7 Execution timed out 2070 ms 28036 KB Time limit exceeded
8 Correct 495 ms 72136 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 30288 KB Output is correct
2 Correct 153 ms 30192 KB Output is correct
3 Correct 142 ms 30200 KB Output is correct
4 Correct 17 ms 16000 KB Output is correct
5 Correct 517 ms 49016 KB Output is correct
6 Correct 446 ms 49000 KB Output is correct
7 Correct 264 ms 48744 KB Output is correct

Subtask #4
16.666667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 19664 KB Output is correct
2 Correct 169 ms 19832 KB Output is correct
3 Correct 691 ms 27256 KB Output is correct
4 Correct 766 ms 27232 KB Output is correct
5 Correct 272 ms 25328 KB Output is correct
6 Execution timed out 2079 ms 25308 KB Time limit exceeded
7 Correct 1362 ms 29528 KB Output is correct
8 Execution timed out 2063 ms 30040 KB Time limit exceeded
9 Execution timed out 2059 ms 37228 KB Time limit exceeded
10 Correct 857 ms 45972 KB Output is correct
11 Execution timed out 2065 ms 24844 KB Time limit exceeded
12 Execution timed out 2060 ms 34084 KB Time limit exceeded
13 Execution timed out 2051 ms 41060 KB Time limit exceeded