| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1079932 |
2024-08-29T03:38:15 Z |
dozer |
Game (IOI13_game) |
C++14 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define ll long long
const int modulo = 1e9 + 7;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Treap{
struct Node{
ll h, b;
Node *l, *r;
ll val;
ll gcdd;
Node(ll ind, ll v){
val = v;
gcdd = v;
b = ind;
h = rand();
l = r = NULL;
};
void pull(){
gcdd = val;
if (l != NULL) gcdd = gcd2(gcdd, l->gcdd);
if (r != NULL) gcdd = gcd2(gcdd, r->gcdd);
}
};
typedef Node* pnode;
pnode root;
Treap(){
root = NULL;
}
void split(pnode node, pnode &L, pnode &R, ll val){
if (node == NULL) return;
if (node->b <= val){
L = node;
pnode tmp = NULL;
split(node->r, tmp, R, val);
L->r = tmp;
}
else{
R = node;
pnode tmp = NULL;
split(node->l, L, tmp, val);
R->l = tmp;
}
if (L != NULL) L->pull();
if (R != NULL) R->pull();
}
void merge(pnode L, pnode R, pnode &res){
if (L == NULL){
res = R;
return;
}
if (R == NULL){
res = L;
return;
}
if (L->h > R->h){
pnode tmp = NULL;;
merge(L->r, R, tmp);
L->r = tmp;
res = L;
}
else{
pnode tmp = NULL;
merge(L, R->l, tmp);
R->l = tmp;
res = R;
}
if (res != NULL) res->pull();
}
ll query(ll l, ll r){
pnode a = NULL, b = NULL, c = NULL, d = NULL;
split(root, a, b, l - 1);
split(b, c, d, r);
ll ans = 0;
if (c != NULL) ans = c->gcdd;
pnode tmp;
merge(a, c, tmp);
pnode tmp2;
merge(tmp, d, root);
return ans;
}
void update(ll ind, ll val){
pnode a = NULL, b = NULL, c = NULL, d = NULL;
split(root, a, b, ind - 1);
split(b, c, d, ind);
if (c == NULL) c = new Node(ind, val);
c->val = val;
c->gcdd = val;
pnode tmp = NULL;
merge(a, c, tmp);
merge(tmp, d, root);
}
};
struct SegTree{
struct Node{
Node *l, *r;
Treap *t;
Node(){
t = new Treap();
l = r = NULL;
}
};
typedef Node* pnode;
ll r;
pnode root;
SegTree(){
root = new Node();
}
SegTree(ll R){
root = new Node();
r = R;
srand(time(NULL));
}
void update(pnode node, ll l, ll r, ll sx, ll sy, ll val){
node->t->update(sy, val);
if (l == r) return;
ll mid = (l + r) / 2;
if (sx <= mid){
if (node->l == NULL) node->l = new Node();
update(node->l, l, mid, sx, sy, val);
}
else{
if (node->r == NULL) node ->r = new Node();
update(node->r, mid + 1, r, sx, sy, val);
}
}
ll query(pnode node, ll l, ll r, ll a, ll b, ll c, ll d){
if (l > b || r < a) return 0;
if (l >= a && r <= b) return node->t->query(c, d);
ll mid = (l + r) / 2;
ll ans = 0;
if (a <= mid && node->l != NULL){
ans = gcd2(ans, query(node->l, l, mid, a, b, c, d));
}
if (b > mid && node->r != NULL){
ans = gcd2(ans, query(node->r, mid + 1, r, a, b, c, d));
}
return ans;
}
void update_util(ll sx, ll sy, ll val){
update(root, 1, r, sx, sy, val);
}
ll query_util(ll a, ll b, ll c, ll d){
return query(root, 1, r, a, b, c, d);
}
};
ll r, c;
SegTree *t;
void init(int R, int C) {
t = new SegTree(R);
r = R, c = C;
}
void update(int P, int Q, long long K) {
t->update_util(P + 1, Q + 1, K);
}
long long calculate(int P, int Q, int U, int V) {
P++, Q++, U++, V++;
return t->query_util(P, U, Q, V);
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_SIZE 1000000000
#define MAX_N 272000
int main() {
int R, C, N;
int P, Q, U, V;
long long K;
int i, type;
int res;
res = scanf("%d", &R);
res = scanf("%d", &C);
res = scanf("%d", &N);
init(R, C);
for (i = 0; i < N; i++) {
res = scanf("%d", &type);
if (type == 1) {
res = scanf("%d%d%lld", &P, &Q, &K);
update(P, Q, K);
} else if (type == 2) {
res = scanf("%d%d%d%d", &P, &Q, &U, &V);
printf("%lld\n", calculate(P, Q, U, V));
} else{
printf("%d\n", type);
fail("Invalid action type in input file.");
}
}
cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
*/
Compilation message
game.cpp: In member function 'long long int Treap::query(long long int, long long int)':
game.cpp:107:9: warning: unused variable 'tmp2' [-Wunused-variable]
107 | pnode tmp2;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
