| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1181779 | sano | 게임 (IOI13_game) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC target("tune=native")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Very tight limit, so I chose to submit the code as I struggled quite a bit with getting AC.
// The most important thing, it seems, is inserting elements in the right way. Inserting them one by one isn't fast enough, so you have to first merge them together and then merge them with the rest.
#include "game.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define shit short int
#define ll long long
#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
//using namespace __gnu_pbds;
//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;
int nsd(int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
class treap {
struct node {
node* l = nullptr;
node *r = nullptr;
int val, key, priority, nsd, key2;
node(int val1, int key1, int key12) {
val = val1, key = key1;
key2 = key12;
priority = rand();
nsd = val1;
}
};
typedef node* pnode;
pnode root = nullptr;
int get_nsd(pnode t) {
if (!t) return 0;
return t->nsd;
}
void update(pnode t) {
if (!t) return;
t->nsd = nsd(nsd(get_nsd(t->l), get_nsd(t->r)), t->val);
return;
}
bool porovnaj(int a1, int a2, int b1, int b2) {
if (a1 == b1) {
return a2 > b2;
}
return a1 > b1;
}
void split(pnode t, int key, int key2, pnode& l, pnode& r) {
if (!t) {
l = r = nullptr;
return;
}
if (porovnaj(t->key, t->key2, key, key2)) {
split(t->l, key, key2, l, t->l);
r = t;
}
else {
split(t->r, key, key2, t->r, r);
l = t;
}
update(t);
return;
}
void merge(pnode& t, pnode l, pnode r) {
if (!l || !r) {
t = l ? l : r;
return;
}
if (l->priority > r->priority) {
merge(l->r, l->r, r);
t = l;
}
else {
merge(r->l, l, r->l);
t = r;
}
update(t);
return;
}
void insert(pnode& t, pnode x) {
if (!t) {
t = x;
return;
}
if (x->priority > t->priority) {
split(t, x->key, x->key2, x->l, x->r);
t = x;
}
else {
insert(porovnaj(t->key, t->key2, x->key, x->key2) ? t->l : t->r, x);
}
update(t);
return;
}
void erase(pnode& t, int key, int key2) {
if (!t) return;
if (t->key == key && t->key2 == key2) {
merge(t, t->l, t->r);
}
else {
erase(porovnaj(t->key, t->key2, key, key2) ? t->l : t->r, key, key2);
}
update(t);
return;
}
public:
void zmen(int key2, int key, int val) {
erase(root, key, key2);
insert(root, new node(val, key, key2));
return;
}
int daj(int a, int b) {
pnode l, r;
l = r = nullptr;
split(root, a, (-1) * NEK, root, r);
split(r, b+1, (-1) * NEK, l, r);
int odp = get_nsd(l);
merge(root, root, l);
merge(root, root, r);
return odp;
}
};
class intervalac {
int n;
struct node {
node* l = nullptr;
node* r = nullptr;
treap in;
};
typedef node* pnode;
pnode root = new node;
void propagate(pnode t) {
if (!t->l) t->l = new node;
if (!t->r) t->r = new node;
return;
}
void zmen(pnode t, int l, int r, int a, int b, int k) {
if (a > r || a < l) return;
t->in.zmen(a, b, k);
if (r == l) return;
propagate(t);
int m = (l + r) / 2;
zmen(t->l, l, m, a, b, k); zmen(t->r, m + 1, r, a, b, k);
return;
}
int daj(pnode t, int l, int r, int a, int b, int c, int d) {
if (a > r || b < l) return 0;
if (a <= l && r <= b) {
return t->in.daj(c, d);
}
propagate(t);
int m = (l + r) / 2;
return nsd(daj(t->l, l, m, a, b, c, d), daj(t->r, m + 1, r, a, b, c, d));
}
public:
void postav(int vel) {
n = vel;
return;
}
void zmen(int p, int q, int k) {
zmen(root, 0, n - 1, p, q, k);
return;
}
int daj(int p, int q, int u, int v) {
return daj(root, 0, n - 1, p, q, u, v);
}
};
intervalac seg;
void init(int r, int c) {
seg.postav(r);
return;
}
void update(int p, int q, int k) {
seg.zmen(p, q, k);
return;
}
int calculate(int p, int q, int u, int v) {
return seg.daj(p, u, q, v);
}
/*
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int r, c, q; cin >> r >> c >> q;
init(r, c);
For(i, q) {
int t; cin >> t;
if (t == 1) {
int p, q, k; cin >> p >> q >> k;
update(p, q, k);
}
if (t == 2) {
int p, q, u, v; cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << '\n';
}
}
return 0;
}*/