Submission #746559

#	Time	Username	Problem	Language	Result	Execution time	Memory
746559		asdf412	Seesaw (JOI22_seesaw)	C++14	0 / 100	771 ms	62020 KiB

seesaw

#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define F first
#define S second

using namespace std;

random_device random_seed;
mt19937 mt(random_seed());

struct tree {

  struct Node {
    pair<int, int> key; // Changed key type to pair<int, int>
    int pri, si;
    ll sum;
    int idx; // Index of the node
    Node *l, *r;

    Node(pair<int, int> k, int i) {
      key = k;
      pri = mt();
      si = 1;
      sum = k.F;
      idx = i;
      l = r = nullptr;
    }
  };
  unordered_map<int, int> mp;

  Node *root = nullptr;

  int siz() { 
    if (mp.empty()) return 0;
    return mp.size(); 
  }

  unordered_map<int, int> getmp() {
    return mp;
  }

  int si(Node *root) {
    if (!root) return 0;
    return root->si;
  }

  ll sum(Node *root) {
    if (!root) return 0;
    return root->sum;
  }

  void upd(Node *root) {
    if (!root) return;
    root->si = 1 + si(root->l) + si(root->r);
    root->sum = root->key.F + sum(root->l) + sum(root->r);
  }

  void split(Node *root, int k, Node *&l, Node *&r) {
    if (!root) {
      l = r = nullptr;
      return;
    }
    if (si(root->l) < k) {
      split(root->r, k - si(root->l) - 1, root->r, r);
      l = root;
    } else {
      split(root->l, k, l, root->l);
      r = root;
    }
    upd(root);
  }

  void merge(Node *&root, Node *l, Node *r) {
    if (!l) {
      root = r;
      return;
    }
    if (!r) {
      root = l;
      return;
    }
    if (l->pri < r->pri) {
      merge(l->r, l->r, r);
      root = l;
    } else {
      merge(r->l, l, r->l);
      root = r;
    }
    upd(root);
  }

  void insert(int i, pair<int, int> k) {
    //cout << "inserted " << i << ' ' << k.F << ' ' << k.S << '\n';
    Node *l, *r, *t = new Node(k, i);
    split(root, i - 1, l, r);
    merge(root, l, t);
    merge(root, root, r);
  }

  void erase(int i) {
    Node *l, *r, *mi;
    split(root, i - 1, l, mi);
    split(mi, 1, mi, r);
    delete mi;
    merge(root, l, r);
  }

  ll getsum(int ql, int qr) {
    Node *l, *r, *mi;
    split(root, ql - 1, l, mi);
    split(mi, qr - ql + 1, mi, r);
    ll sum = mi->sum;
    merge(root, l, mi);
    merge(root, root, r);
    return sum;
  }

  pair<int, int> access(int i) {
    Node *curr = root;
    while (curr) {
      int l = si(curr->l);
      if (l == i) {
        return curr->key;
      } else if (l < i) {
        curr = curr->r;
        i -= l + 1;
      } else {
        curr = curr->l;
      }
    }
    return make_pair(-1, -1); // Index out of range
  }

  int lob(pair<int, int> val) {
    Node *curr = root;
    int result = 0;
    while (curr) {
      if (curr->key < val) {
        result += si(curr->l) + 1;
        curr = curr->r;
      } else {
        curr = curr->l;
      }
    }
    return result + 1;
    
  }

  void insert1(int pos, int val) {
    auto it = mp.find(pos);
    //int lo = lowerBoundIndex({val, -1});
    
    if (it == mp.end()) {
      int id = lob({val, pos});
      //cout << "not found wor low " << id << '\n';
      if (id == -1) insert(mp.size() + 1, {val, pos});
      else insert(id, {val, pos});
      mp[pos] = val;
      return;
    } 

    ii tmp = {mp[pos], pos};
    int lo = lob(tmp);
    erase(lo);
    int id = lob({val, pos});
    //if (mp[pos] < val) lo--;
    //cout << "wor low " << id << ' ' << lo  << ' ' << mp[pos] << '\n';
    
    if (lo == -1) lo = mp.size();
    if (id == -1) insert(mp.size() + 1, {val, pos});
    else insert(id, {val, pos});
    mp[pos] = val;
  }

  ll sum1(int a, int b) {
    int l = lob({a, 0});
    int r = lob({b, 1e9});
    //ii tk = access(r);
    r--;
    //if (t.F > b) r--; 
    //cout << "low sum " << l << ' ' << r << '\n';   
    if (l > r) return 0;
    //if (l == r) return tk.F;
    return getsum(l, r);
  }

  void prn(Node *root) {
    if (!root) return;
    upd(root);
    prn(root->l);
    cout << "[ " << root->key.F << ' ' << root->key.S << " ] ";
    prn(root->r);
  }

  void prn1(Node *root) {
    if (!root) return;
    upd(root);
    prn(root->l);
    cout << root->key.S << ' ';
    prn(root->r);
  }

  void prn() {
    cout << " treap \n";
    prn(root);
    cout << '\n';
    //prn1(root);
    cout << '\n';
  }
};

int N, Q;

struct Seg {
  tree t;
  int lo, hi;
  int il = -1, ir = -1;

  Seg(int a, int b) : lo(a), hi(b) {}

  Seg() : lo() {}
};

int curr = 0;

Seg seg[200000];

void upd(int idx, int pos, int val) {
  int l = seg[idx].lo, r = seg[idx].hi, mi = (l + r) >> 1;

  if (l == r) {
    seg[idx].t.insert1(pos, val);
    return;
  }
  
  int tr = (pos <= mi ? seg[idx].il : seg[idx].ir);
  bool lr = pos <= mi ? 1 : 0; // 1 left 0 right
  if (tr == -1) {
    curr++;
    if (lr) seg[idx].il = curr;
    else seg[idx].ir = curr;
    seg[curr] = Seg(pos, pos);
    seg[curr].t.insert1(pos, val);
  } else if (seg[tr].lo <= pos && pos <= seg[tr].hi) {
    upd(tr, pos, val);
  } else {
    do {
      if (pos <= mi) r = mi;
      else l = mi + 1;
      mi = (l + r) >> 1;
    } while ((pos <= mi) == (seg[tr].lo <= mi));

    curr++;
    seg[curr] = Seg(l, r);
    if (seg[tr].lo <= mi) seg[curr].il = tr;
    else seg[curr].ir = tr;

    if (lr) seg[idx].il = curr;
    else seg[idx].ir = curr;
    upd(curr, pos, val);
  }  
  //cout << "updateerror in " << l << ' ' << r << '\n';
  seg[idx].t.insert1(pos, val);
  int tl = seg[idx].il, trr = seg[idx].ir;
  int sil = seg[tl].t.siz();
  int sir = seg[trr].t.siz();
  if (sil + sir != seg[idx].t.siz()) {
    unordered_map<int, int> tm, tm1;
    if (tl != -1) tm = seg[tl].t.getmp();
    if (trr != -1) tm1 = seg[trr].t.getmp();
    for (auto i : tm) seg[idx].t.insert1(i.F, i.S);
    for (auto i : tm1) seg[idx].t.insert1(i.F, i.S);
  }
  

  /*
  if (root->l == NULL)
    root->l = new Seg(l, mi);
  if (root->r == NULL)
    root->r = new Seg(mi + 1, r);

  if (pos <= mi) upd(root->l, pos, val);
  else upd(root->r, pos, val);
  root->t.insert1(pos, val);
  */

  //root->t.prn();
}

ll qur(int idx, int ql, int qr, int a, int b) {
  if (idx == -1) return 0;
  int l = seg[idx].lo, r = seg[idx].hi, mi = (l + r) >> 1;

  //cout << "error in " << l << ' ' << r << '\n';
  //root->t.prn();
  
  if (l > qr || r < ql) 
    return 0;

  if (ql <= l && r <= qr) {
    ll ts = seg[idx].t.sum1(a, b);
    //cout << "return " << ts << '\n';
    return ts;
  }

  return qur(seg[idx].il, ql, qr, a, b) + qur(seg[idx].ir, ql, qr, a, b);
}

int cal(ll x) {
  return abs((x - 69) % min(420, N / 8 + 1));
}

using namespace chrono;


void prn(int idx) {
  if (idx == -1) return;
  prn(seg[idx].il);
  cout << "range : " << seg[idx].lo << ' ' << seg[idx].hi << '\n';
  seg[idx].t.prn();
  prn(seg[idx].ir);

}

void prn1(int idx) {
  cout << "currently seg \n";
  prn(idx);
  cout << '\n';
}

int ar[5005];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  auto start = high_resolution_clock::now();
  
  //freopen("9.in", "r", stdin);
  //freopen("t3.sol", "w", stdout);

  
  N = 1e9, Q = 5e4;

  seg[0].lo = 0; seg[0].hi = N;
  int C = 0;
  while (Q--) {
    int X = mt(); 
    if (X&1 == 1) {
      int Pos = mt() % N, Val = mt(); 
      upd(0, Pos, Val);
    }
    else {
      int L, R, A, B;
      L = mt() % N, R = mt() % N, A = mt(), B = mt();
      if (L > R) swap(L, R);
      L += C; R += C;
      ll sum = qur(0, L, R, A, B);
      R = min(R, N);
      C = cal(sum);
      //cout << "sum of range " << C << ' ' << L << ' ' << R << " = " << sum << '\n';
      //cout << sum << '\n';
    }    
  }
  
  
  
  /*
  cin >> N >> Q;
  //if (N <= 10000) N = 10000;
  //Seg *root = new Seg(0, N); 
  seg[0].lo = 0; seg[0].hi = N;
  
  int C = 0;
  while (Q--) {
    int X; cin >> X;
    if (X == 1) {
      int Pos, Val; 
      cin >> Pos >> Val;
      upd(0, Pos, Val);
    } else {
      int L, R, A, B;
      cin >> L >> R >> A >> B;
      L += C; R += C;
      ll sum = qur(0, L, R, A, B);
      R = min(R, N);
      C = cal(sum);
      //cout << "sum of range " << C << ' ' << L << ' ' << R << " = " << sum << '\n';
      cout << sum << '\n';
      //prn1(0);
    }    
    
  }

  */

  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);

  cout << "Time taken by program: " << double(duration.count())/1000000 << " seconds\n"; 
  cout << curr << '\n';

  return 0;
}

/*
10 7
1 1 3
1 2 5
1 9 4
2 2 5 2 5
1 7 5
1 5 7
2 4 8 6 10

5
7

3 5 4 5 7 9 4 2 5 6

*/

Compilation message (stderr)

seesaw.cpp: In function 'long long int qur(int, int, int, int, int)':
seesaw.cpp:293:41: warning: unused variable 'mi' [-Wunused-variable]
  293 |   int l = seg[idx].lo, r = seg[idx].hi, mi = (l + r) >> 1;
      |                                         ^~
seesaw.cpp: In function 'int main()':
seesaw.cpp:348:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  348 |     if (X&1 == 1) {
      |           ~~^~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33