| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 746206 |
2023-05-21T22:21:39 Z |
asdf412 |
Seesaw (JOI22_seesaw) |
C++14 |
|
583 ms |
47148 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 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
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) {
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
47148 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
47148 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
47148 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
47148 KB |
Expected double, but "Time" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
