Submission #101893

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<(b)?(a=b,1):0)
#define chmin(a,b) (a>(b)?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

typedef unsigned int uint;
uint xorshift() {
  static uint x=123456789,y=362436069,z=521288629,w=88675123; 
  uint t=(x^(x<<11));x=y;y=z;z=w;
  return ( w=(w^(w>>19))^(t^(t>>8)) ); 
}
template<class T>
struct Treap {
  struct Node {
    T val, sum;
    Node *ch[2];
    uint pri; // prioriry
    int cnt; // size of tree
    Node() { init((T)0); }
    Node(const T &v) { init(v); }
    void init(const T &v) {
      pri = xorshift();
      val = sum = v;
      ch[0] = ch[1] = NULL;
      cnt = 1;
    }
  } *root;
  void toStrSub(Node *n, stringstream &ss) const {
    if (!n) ss << "*";
    else {
      ss << n->val;
      if (n->ch[0] || n->ch[1]) {
        ss << "(";
        toStrSub(n->ch[0], ss);
        ss << ",";
        toStrSub(n->ch[1], ss);
        ss << ")";
      }
    }    
  }
  string toStr(Node *n) const {
    stringstream ss;
    toStrSub(n, ss);
    return ss.str();
  }; 
  Treap() : root(NULL) {}
  Treap(T v): root(new Node(v)) {}
  void init(T v) { root = new Node(v); }

  int count(Node *t) { return t ? t->cnt : 0;}
  T sum(Node *t) { return t ? t->sum : 0; }

  Node *update(Node *n) {
    if (!n) return n;
    n->cnt = count(n->ch[0]) + count(n->ch[1]) + 1;
    n->sum = sum(n->ch[0]) + sum(n->ch[1]) + n->val;
    return n;
  }
  Node *link(Node *n, Node *c, int b) { n->ch[b] = update(c); return update(n); }
  Node *merge(Node *l, Node *r) {
    if (!l || !r) return l ? l : r;
    if (l->pri > r->pri) return link(l, merge(l->ch[1],r), 1);
    else return link(r, merge(l, r->ch[0]), 0);
  }
  typedef pair<Node*, Node*> pNN;
  // at group
  // consider position of the node
  pNN splitAt(Node *n, const int k) { // [0,k) [k,n)
    if (!n) return pNN(n,n);
    if (k <= count(n->ch[0])) {
      pNN s = splitAt(n->ch[0], k);
      return make_pair(s.first, link(n, s.second, 0));
    } else {
      pNN s = splitAt(n->ch[1], k - count(n->ch[0]) - 1);
      return make_pair(link(n, s.first, 1), s.second);
    }
  }
  T getFirst() {
    pNN p = splitAt(root, root->cnt/2);
    T r = p.first->sum;
    root = merge(p.first, p.second);
    return r;
  }
  Node *insertAt(Node *n, int k, T v) {
    pNN s = splitAt(n, k);
    Node *node = new Node(v);
    return merge(merge(s.first, node), s.second);
  }
  Node *eraseAt(Node *n, const int k) {
    pNN s = splitAt(n, k);
    return merge(s.first, splitAt(s.second, 1).second);
  }
  T kth(Node *n, const int k) { // k>=0
    pNN s = splitAt(n, k);
    pNN t = splitAt(s.second,1);
    Node *tmp = t.first;
    n = merge(s.first, merge(t.first, t.second));
    return tmp ? tmp->val : 0;  // 0 ???
  }
  void insertAt(int k, T v) { root = insertAt(root, k, v);  }
  void eraseAt(const int k) { root = eraseAt(root, k); }

  void shuffle(int k) {
    pNN p = splitAt(root, k);
    root = merge(p.second, p.first);
  }
  
  T kth(const int k) { return k<0?0:kth(root, k); }
  // normal group
  // consider val of the node
  pNN split(Node *n, T v) { // [,v) [v,)
    if (!n) return pNN(n,n);
    if (n->val >= v) {
      pNN s = split(n->ch[0], v);
      return make_pair(s.first, link(n, s.second, 0));      
    } else {
      pNN s = split(n->ch[1], v);
      return make_pair(link(n, s.first, 1), s.second);      
    }
  }
  Node *insert(Node *n, T v) {
    pNN s = split(n,v);
    Node *node = new Node(v);
    return merge(merge(s.first, node), s.second);
  }
  Node *eraseAll(Node *n, T v) { // erase all the nodes that have v
    pNN s = split(n, v);
    return merge(s.first, split(s.second, v+1).second); // T = int ????
    // Tが整数でないときは [,v] (v,) なsplitを使う
  }
  Node *erase(Node *n, T v) { // erase one of the nodes that have v
    pNN s = split(n,v);
    pNN t = split(s.second, v+1);
    t.first = eraseAt(t.first, 0);
    return merge(s.first, merge(t.first, t.second));
  }
  Node *merge2(Node *dst, Node *src) { // SIZE(src) should be less than SIZE(dst) O(nlogn)
    if (!src) return dst;
    REP(i,2) dst = merge2(dst, src->ch[i]);
    dst = insert(dst, src->val);
    return dst;
  }
  void insert(T v) { root = insert(root, v); }
  void eraseAll(T v) { root = eraseAll(root, v); }
  void erase(T v) { root = erase(root, v); }
  void merge2(Node *n) {
    if (count(root) < count(n)) swap(root, n);
    root = merge2(root, n);
  }
};
template <class T>
ostream& operator<<(ostream &os, const Treap<T> &t) {
  os << t.toStr(t.root);
  return os;
}

int main() {
  int n,m;
  while(cin >> n >> m) {
    Treap<ll> treap;
    REP(i,n) {
      int a;scanf("%d",&a);
      treap.insertAt(i, a);
    }
    //cout << treap << endl;
    ll res = -(1LL<<60);
    chmax(res, treap.getFirst());
    REP(i,m) {
      int a; scanf("%d", &a);
      a--;
      treap.shuffle(a);
      // REP(j,10) cout << treap.kth(j) << " "; cout << endl;
      // cout << treap << endl;
      ll p = treap.getFirst();
      //cout << p << endl;
      chmax(res, p);
    }
    cout << res << endl;
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:190:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:197:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result