Submission #746206

#	Time	Username	Problem	Language	Result	Execution time	Memory
746206		asdf412	Seesaw (JOI22_seesaw)	C++14	0 / 100	583 ms	47148 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 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;
  Seg *l = NULL, *r = NULL;

  Seg(int a, int b) {
    lo = a; hi = b;
  }
};

void upd(Seg *root, int pos, int val) {
  int l = root->lo, r = root->hi, mi = (l + r) >> 1;

  if (l == r) {
    root->t.insert1(pos, val);
    return;
  }

  
  Seg **tr = &(pos <= mi ? root->l : root->r);
  if (*tr == NULL) {
    *tr = new Seg(pos, pos);
    (*tr)->t.insert1(pos, val);
  } else if ((*tr)->lo <= pos && pos <= (*tr)->hi) {
    upd(*tr, pos, val);
  } else {
    do {
      if (pos <= mi) r = mi;
      else l = mi + 1;
      mi = (l + r) >> 1;
    } while ((pos <= mi) == ((*tr)->lo <= mi));

    Seg *nn = new Seg(l, r);
    if ((*tr)->lo <= mi) nn->l = *tr;
    else nn->r = *tr;
    *tr = nn;
    upd(*tr, pos, val);
  }
  root->t.insert1(pos, val);
  

  /*
  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(Seg *root, int ql, int qr, int a, int b) {
  if (root == NULL) return 0;
  int l = root->lo, r = root->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 = root->t.sum1(a, b);
    //cout << "return " << ts << '\n';
    return ts;
  }

  return qur(root->l, ql, qr, a, b) + qur(root->r, ql, qr, a, b);
}

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

using namespace chrono;

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

  
  N = 1e9, Q = 5e4;

  Seg *root = new Seg(0, N);
  int C = 0;
  while (Q--) {
    int X = mt(); 
    if (X&1 == 1) {
      int Pos = mt() % N, Val = mt(); 
      upd(root, 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(root, 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);
  
  int C = 0;
  while (Q--) {
    int X; cin >> X;
    if (X == 1) {
      int Pos, Val; 
      cin >> Pos >> Val;
      upd(root, Pos, Val);
    }
    else {
      int L, R, A, B;
      cin >> L >> R >> A >> B;
      L += C; R += C;
      ll sum = qur(root, L, R, A, B);
      R = min(R, N);
      C = cal(sum);
      //cout << "sum of range " << C << ' ' << L << ' ' << R << " = " << sum << '\n';
      cout << sum << '\n';
    }    
  }

  */

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

  cout << "Time taken by program: " << double(duration.count())/1000000 << " seconds\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(Seg*, int, int, int, int)':
seesaw.cpp:263:35: warning: unused variable 'mi' [-Wunused-variable]
  263 |   int l = root->lo, r = root->hi, mi = (l + r) >> 1;
      |                                   ^~
seesaw.cpp: In function 'int main()':
seesaw.cpp:300:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  300 |     if (X&1 == 1) {
      |           ~~^~~~

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