| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 746559 |
2023-05-22T18:51:50 Z |
asdf412 |
Seesaw (JOI22_seesaw) |
C++14 |
|
771 ms |
62020 KB |
#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
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) {
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
771 ms |
62020 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
771 ms |
62020 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
771 ms |
62020 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
771 ms |
62020 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
