| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 962807 |
2024-04-14T08:30:03 Z |
Ice_man |
Game (IOI13_game) |
C++14 |
|
1126 ms |
159180 KB |
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include "game.h"
#include <map>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <random>
#define maxn 22001
#define maxr 20000005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;
#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")
using namespace std;
/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}*/
typedef long long ll;
mt19937 mt(time(nullptr));
int rands[maxr];
int lastr;
struct Node
{
int p , key;
int left , right;
Node *l , *r;
ll a;
ll gcd;
Node()
{
l = nullptr;
r = nullptr;
}
Node(int _pos , ll _a)
{
l = nullptr;
r = nullptr;
left = _pos;
right = _pos;
p = _pos;
a = _a;
gcd = _a;
key = rands[lastr];
lastr++;
}
void pull()
{
gcd = a;
left = p;
right = p;
if(l != nullptr)
gcd = __gcd(gcd , l -> gcd);
if(r != nullptr)
gcd = __gcd(gcd , r -> gcd);
if(l != nullptr)
left = l -> left;
if(r != nullptr)
right = r -> right;
}
};
struct treap
{
Node *root;
void split(Node *node , int qp , Node* &left , Node* &right)
{
if(node == nullptr)
{
left = nullptr;
right = nullptr;
return;
}
if(node -> p < qp)
{
split(node -> r , qp , left , right);
node -> r = left;
left = node;
}
else
{
split(node -> l , qp , left , right);
node -> l = right;
right = node;
}
node -> pull();
}
Node* _merge(Node *left , Node *right)
{
if(left == nullptr)
return right;
if(right == nullptr)
return left;
if(left -> key < right -> key)
{
left -> r = _merge(left -> r , right);
left -> pull();
return left;
}
else
{
right -> l = _merge(left , right -> l);
right -> pull();
return right;
}
}
void update(Node *node , int qp , ll qval)
{
if(node -> p == qp)
{
node -> a = qval;
node -> pull();
return;
}
if(node -> p > qp)
update(node -> l , qp , qval);
else
update(node -> r , qp , qval);
node -> pull();
}
bool _find(int qp)
{
Node *pom = root;
while(pom != nullptr)
{
if(pom -> p == qp)
return true;
if(pom -> p > qp)
pom = pom -> l;
else
pom = pom -> r;
}
return false;
}
ll fake_query(Node *node , int ql , int qr)
{
if(node -> right < ql || qr < node -> left)
return 0;
if(ql <= node -> left && node -> right <= qr)
return node -> gcd;
ll q = 0;
if(ql <= node -> p && node -> p <= qr)
q = node -> a;
if(node -> l != nullptr)
q = __gcd(q , fake_query(node -> l , ql , qr));
if(node -> r != nullptr)
q = __gcd(q , fake_query(node -> r , ql , qr));
return q;
}
void add(int qp , ll qval)
{
if(_find(qp) == true)
update(root , qp , qval);
else
{
Node *poml , *pomr;
split(root , qp , poml , pomr);
root = _merge(_merge(poml , new Node(qp , qval)) , pomr);
}
}
ll query(int ql , int qr)
{
if(root == nullptr)
return 0;
return fake_query(root , ql , qr);
}
treap()
{
root = nullptr;
}
};
struct tr
{
tr *l , *r;
treap node;
int li , ri;
tr(int ql , int qr)
{
l = nullptr;
r = nullptr;
li = ql;
ri = qr;
}
void makel()
{
if(l == nullptr)
l = new tr(li , (li + ri) / 2);
}
void maker()
{
if(r == nullptr)
r = new tr((li + ri) / 2 + 1 , ri);
}
ll query(int xl , int xr , int ql , int qr)
{
if(ri < xl || xr < li)
return 0;
if(xl <= li && ri <= xr)
return node.query(ql , qr);
ll a = 0;
if(l != nullptr)
a = __gcd(a , l -> query(xl , xr , ql , qr));
else
a = __gcd(a , r -> query(xl , xr , ql , qr));
return a;
}
void pull(int qp)
{
ll a = 0;
if(l != nullptr)
a = __gcd(a , l -> node.query(qp , qp));
if(r != nullptr)
a = __gcd(a , r -> node.query(qp , qp));
node.add(qp , a);
}
void update(int ql , int qr , ll qval)
{
if(ri < ql || ql < li)
return;
if(li == ri)
{
node.add(qr , qval);
return;
}
int mid = (li + ri) / 2;
if(ql <= mid)
{
makel();
l -> update(ql , qr , qval);
}
else
{
maker();
r -> update(ql , qr , qval);
}
pull(qr);
}
tr()
{
l = nullptr;
r = nullptr;
}
};
tr tree;
void init(int R , int C)
{
for(int i = 0; i < maxr; i++)
rands[i] = i;
random_shuffle(rands , rands + maxr);
tree = tr(0 , R - 1);
}
void update(int P , int Q , ll K)
{
tree.update(P , Q , K);
}
ll calculate(int P , int Q , int U , int V)
{
return tree.query(P , U , Q , V);
}
/**int main()
{
#ifdef ONLINE_JUDGE /// promeni
freopen("input.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//startT = std::chrono::high_resolution_clock::now();
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
966 ms |
78696 KB |
Output is correct |
| 2 |
Incorrect |
934 ms |
78700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
951 ms |
78692 KB |
Output is correct |
| 2 |
Correct |
918 ms |
78692 KB |
Output is correct |
| 3 |
Runtime error |
1000 ms |
159180 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1126 ms |
78712 KB |
Output is correct |
| 2 |
Incorrect |
904 ms |
78696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
909 ms |
78696 KB |
Output is correct |
| 2 |
Incorrect |
947 ms |
78700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
935 ms |
78696 KB |
Output is correct |
| 2 |
Incorrect |
903 ms |
78696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
